Quelle small.gi Sprache: unbekannt

#############################################################################
##
##  small.gi                       Smallsemi - a GAP library of semigroups
##  Copyright (C) 2008-2024            Andreas Distler & James D. Mitchell
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##

# Returns the integer represented by <str> with characters in [0-<bas>].
BindGlobal("SMALLSEMI_BinInt",
function(str, bas)
  local int, pot, c;

  int := 0;
  pot := 1;
  str := Reversed(str);
  for c in str do
    int := int + pot * Int([c]);
    pot := pot * bas;
  od;

  return int;
end);

# returns an isomorphism to a semigroup from the library if such exists
# and an anti-isomorphism otherwise
InstallMethod(EquivalenceSmallSemigroup, "for a small semigroup",
[IsSmallSemigroup], IdentityMapping);

InstallMethod(EquivalenceSmallSemigroup, "for a semigroup", [IsSemigroup],
function(S)
  local size, nr, mt, stab, orbit, diag, perm, diaglits, pos, translits,
      n, k, strlist, offset, line, i, tbllits, phi, small, transorbit, isIso,
      equi, LitNum, NumLit, tbl2lits, diag2lits, onLiterals, is3nilpotent,
      BinInt, imglist, ListToMatrix;

  LitNum := function(ln, n)
    return [QuoInt(ln - 1, n ^ 2) + 1,
            QuoInt((ln - 1) mod n ^ 2, n) + 1, (ln - 1) mod n + 1];
  end;

  NumLit     := {lit, n} -> (lit[1] - 1) * n ^ 2 + (lit[2] - 1) * n + lit[3];
  diag2lits  := {diag, n} -> List([1 .. n], i -> NumLit([i, i, diag[i]], n));
  tbl2lits   := {table, n} -> SMALLSEMI_TableToLiterals(table, n, NumLit);
  onLiterals := n -> SMALLSEMI_OnLiterals(n, LitNum, NumLit);

  is3nilpotent := function(table)
    local n, zero, entries, i;

    n := Size(table);
    zero := First([1 .. n], i -> table[i] = ListWithIdenticalEntries(n, i)
                  and table{[1 .. n]}[i] = ListWithIdenticalEntries(n, i));
    if zero = fail then
      return false;
    else
      entries := Difference(Unique(Flat(table)), [zero]);
      # zero semigroup is 2-nilpotent
      if IsEmpty(entries) then
        return false;
      fi;
      for i in entries do
        if table[i] <> ListWithIdenticalEntries(n, zero) or
            table{[1 .. n]}[i] <> ListWithIdenticalEntries(n, zero) then
          return false;
        fi;
      od;
    fi;
    return true;
  end;

  BinInt := SMALLSEMI_BinInt;

  ListToMatrix := function(line)
    local mat, ord, i;

    ord := RootInt(Length(line));
    mat := EmptyPlist(ord);

    for i in [1 .. ord] do
      Add(mat, line{[1 + (i - 1) * ord .. i * ord]});
    od;

    return mat;
  end;

  if Size(S) > 8 then
    Error("only semigroups with up to 8 elements are contained in",
          " the library.");
  fi;

  # special case trivial semigroup
  if Size(S) = 1 then
    small := SmallSemigroup(1, 1);
    equi := SemigroupHomomorphismByImagesNC(S, small, Elements(S));
    SetIsBijective(equi, true);
    return equi;
  fi;

  n := Size(S);
  mt := MultiplicationTable(S);
  diag := DiagonalOfMat(mt);
  phi := ActionHomomorphism(SymmetricGroup(n), [1 .. n ^ 3], onLiterals(n));

  # get minimal representative of diagonal
  diaglits := diag2lits(diag, n);
  orbit := Orbit(Image(phi), diaglits, OnSets);
  perm := RepresentativeAction(Image(phi), diaglits, Minimum(orbit), OnSets);
  diag := List(Minimum(orbit), x -> LitNum(x, n)[3]);

  # work with stabiliser of new diagonal on changed table
  tbllits := tbl2lits(mt, n);
  tbllits := OnSets(tbllits, perm);
  translits := List(tbllits, lit -> LitNum(lit, n));
  translits := List(translits, lit -> NumLit([lit[2], lit[1], lit[3]], n));
  translits := AsSet(translits);
  stab := Stabilizer(Image(phi), Minimum(orbit), OnSets);

  # search in list of isomorphic multiplication tables with same diagonal
  orbit := Orbit(stab, tbllits, OnSets);
  # .. . and anti - isomorphic
  transorbit := Orbit(stab, translits, OnSets);

  # determine whether minimum is isomorphic or anti - isomorphic
  if Minimum(orbit) > Minimum(transorbit) then
      isIso := false;
      perm := perm * RepresentativeAction(Image(phi),
                                          translits,
                                          Minimum(transorbit),
                                          OnSets);
      # the equivalent table stored in smallsemi as list
      mt := List(Minimum(transorbit), x -> LitNum(x, n)[3]);
  else
      isIso := true;
      perm := perm * RepresentativeAction(Image(phi),
                                          tbllits,
                                          Minimum(orbit),
                                          OnSets);
      # the equivalent table stored in smallsemi as list
      mt := List(Minimum(orbit), x -> LitNum(x, n)[3]);
  fi;

  # rest of code expects a matrix, not a list
  mt := ListToMatrix(mt);

  size := n;
  # extract from the minimal table the string which is stored in the library
  if size <= 7 or not is3nilpotent(mt) then
    pos := Position(MOREDATA2TO8[size].diags, diag);
    offset := MOREDATA2TO8[size].endpositions[pos];
    # ensure data is loaded
    RecoverMultiplicationTableNC(size, offset + 1);
    if size <= 7 then
      strlist := DATA2TO7[size - 1];
      strlist := List(strlist, st -> st{[offset + 1 .. Length(st)]});
      # translate table to string
      line := Concatenation(List(Flat(mt - 1), String));
      # first entry is always equal 1 and thus not stored
      Remove(line, 1);
    else
      strlist := DATA8[pos];
      line := Concatenation(List(Flat(mt - 1), String));
      # all non - diagonal entries are stored
      for i in [1 .. 8] do
        Remove(line, 1 + (i - 1) * 8);
      od;
    fi;
  else
    k := First([1 .. 8], i -> mt[i] <> [1, 1, 1, 1, 1, 1, 1, 1] or
                              mt{[1 .. 8]}[i] <> [1, 1, 1, 1, 1, 1, 1, 1]);
    ## special case 2 nilpotent semigroup
    ## if k = fail then return [ size, NrSmallSemigroups(8) ]; fi;
    pos := Position(MOREDATA2TO8[8].3nildiags, diag{[k .. 8]});
    offset := MOREDATA2TO8[8].3nilendpositions[pos] + 11433106;
    # ensure data is loaded
    RecoverMultiplicationTableNC(size, offset + 1);
    strlist := 3NIL_DATA.strlist;
    # only non-diagonal entries of the non zero row-columns are stored
    line := Concatenation(List(Flat(mt{[k .. 8]}{[k .. 8]} - 1), String));
    for i in [1 .. 8 - k + 1] do
      Remove(line, 1 + (i - 1) * (8 - k + 1));
    od;
  fi;

  # search for the position of the string in the data lists
  if size <= 7 or not is3nilpotent(mt) then
    pos := 1;
    for i in [1 .. Length(line)] do
      while strlist[i][pos] < line[i] do
        pos := pos + 1;
      od;
    od;
  else
    pos := 1;
    for i in [1 .. Length(line)] do
      while IsBound(strlist[i][pos]) and strlist[i][pos] < line[i]
          and (not IsBound(strlist[i][pos + 1])
          or strlist[i][pos] <= strlist[i][pos + 1]) do
        pos := pos + 1;
      od;
      if not IsBound(strlist[i][pos]) or strlist[i][pos] > line[i] then
        pos := pos - 1;
      fi;
    od;
  fi;

  # fine tuning
  while List(strlist, st -> st[pos]) < line and IsBound(strlist[1][pos + 1]) do
    pos := pos + 1;
  od;
  while List(strlist, st -> st[pos]) > line do
    pos := pos - 1;
  od;

  # correct number in current data (depending on diagonal) by offset
  if size <= 7 or not is3nilpotent(mt) then
    nr := pos + offset;
  else
    nr := 3NIL_DATA.positions[pos] + offset + BinInt(line, k - 1) -
          BinInt(List(strlist, st -> st[pos]), k - 1);
    # for safety reasons ...
    while mt <> RecoverMultiplicationTableNC(8, nr) do
      Info(InfoSmallsemi, 1,
           "IdSmallSemigroup: That shouldn't really happen.");
      nr := nr + 1;
    od;
  fi;

  # the bijection mapping the input or its transposed to a small semigroup
  equi := PreImages(phi, [perm])[1];
  small := SmallSemigroup(size, nr);
  imglist := Permuted(AsSSortedList(small), equi ^ -1);
  if isIso then
    equi := SemigroupHomomorphismByImagesNC(S, small, imglist);
    SetIsBijective(equi, true);
  else
    equi := MappingByFunction(S,
                              small,
                              x -> imglist[Position(AsSSortedList(S), x)]);
    SetRespectsMultiplication(equi, false);
    SetIsBijective(equi, true);
  fi;

  return equi;
end);

InstallMethod(IdSmallSemigroup, "for a semigroup", [IsSemigroup],
s -> IdSmallSemigroup(Range(EquivalenceSmallSemigroup(s))));

SetInfoLevel(InfoSmallsemi, 1);

InstallMethod(IsomorphismTransformationSemigroup, [IsSmallSemigroup],
function(S)
  local table, map, T, iso;

  table := TransposedMat(MultiplicationTable(S));
  map   := x -> TransformationNC(Concatenation(table[x!.index], [x!.index]));
  T     := Semigroup(List(MinimalGeneratingSet(S), map));
  SetSize(T, Size(S));
  SetMultiplicationTable(T, MultiplicationTable(S));
  SetIdSmallSemigroup(T, IdSmallSemigroup(S));
  UseIsomorphismRelation(S, T);

  iso := SemigroupHomomorphismByImagesNC(S, T, List(AsSSortedList(S), map));
  SetIsBijective(iso, true);

  return iso;
end);

InstallGlobalFunction(RecoverMultiplicationTable, function(size, nr)
  local numbers;

  # numbers of semigroups of sizes 1 - 8
  numbers := [1, 4, 18, 126, 1160, 15973, 836021, 1843120128];

  if size > 8 or nr > numbers[size] then
    return fail;
  fi;
  return RecoverMultiplicationTableNC(size, nr);
end);

InstallGlobalFunction(RecoverMultiplicationTableNC,
function(size, nr)
  local flatmat, ListToMatrix, i, data, file, pos, diag, k, mat,
  int, rem, line, m, j;

  if size = 1 then
    return [[1]];
  fi;

  # converts a list into the corresponding multiplication table
  ListToMatrix := function(line)
    local mat, i;

    mat := EmptyPlist(size);

    for i in [1 .. size] do
      Add(mat, line{[1 + (i - 1) * size .. i * size]});
    od;

    return mat;
  end;

    # check whether data is already available, read otherwise
  if size < 8 then
    if not IsBound(DATA2TO7[size - 1]) then
      if size = 7 then
        Info(InfoSmallsemi, 1,
             "Smallsemi: loading data for semigroups of size 7.");
      fi;
      file := Filename(DirectoriesPackageLibrary("smallsemi",
                                                 "data/data2to7"),
                       Concatenation("data", String(size), ".gl"));
      DATA2TO7[size - 1] := SplitString(StringFile(file), "\n");
      # remove copyright
      Remove(DATA2TO7[size - 1], 1);
    fi;
    data := DATA2TO7[size - 1];

  elif nr <= 11433106 then  # size = 8
      pos := PositionProperty(MOREDATA2TO8[8].endpositions, i -> i >= nr);
      diag := MOREDATA2TO8[8].diags[pos - 1];
      if pos - 1 <> PositionBound(DATA8) then
          if IsInt(PositionBound(DATA8)) then
              Unbind(DATA8[PositionBound(DATA8)]);
          fi;
          Info(InfoSmallsemi, 1,
                "Smallsemi: loading data for semigroups of size 8.");
          file := Filename(DirectoriesPackageLibrary("smallsemi",
                                                     "data/data8"),
                           Concatenation("8diag",
                                         Concatenation(List(diag, String)),
                                         ".gl"));
          DATA8[pos - 1] := SplitString(StringFile(file), "\n");
          # remove copyright
          Remove(DATA8[pos - 1], 1);
      fi;
      data := DATA8[pos - 1];
      nr := nr - MOREDATA2TO8[8].endpositions[pos - 1];

    else  # 3 - nilpotent semigroup
        # CODE HAS TO BE REVISED, UGLY CODING AND MISLEADING VARIABLE NAMES AD
        # get correct diagonal, adjust number
        nr := nr - 11433106;
        pos := PositionProperty(MOREDATA2TO8[8].3nilendpositions, i -> i >= nr);
        diag := MOREDATA2TO8[8].3nildiags[pos - 1];
        if diag <> 3NIL_DATA.diag then
            Info(InfoSmallsemi, 1,
                  "Smallsemi: loading data for semigroups of size 8.");
            READ_3NIL_DATA(diag);
        fi;
        nr := nr - MOREDATA2TO8[8].3nilendpositions[pos - 1];
        # search from which stored solution to start from
        for pos in [3NIL_DATA.next .. Length(3NIL_DATA.positions)] do
            if 3NIL_DATA.positions[pos - 1] <= nr
               and 3NIL_DATA.positions[pos] > nr then
                3NIL_DATA.next := pos;
                pos := pos - 1;
                break;
            fi;
        od;
        if Length(3NIL_DATA.positions) = 1 then
          pos := 1;
        fi;
        if 3NIL_DATA.positions[pos] > nr then
            for pos in [1 .. 3NIL_DATA.next - 1] do
                if 3NIL_DATA.positions[pos] > nr then
                    3NIL_DATA.next := pos;
                    pos := pos - 1;
                    break;
                fi;
            od;
        elif 3NIL_DATA.next <> pos + 1 then
            3NIL_DATA.next := pos;
        fi;

        m := Length(3NIL_DATA.diag);
        line := List([1 .. m ^ 2 - m], i -> 3NIL_DATA.strlist[i][pos]);

        int := SMALLSEMI_BinInt(line, 8 - m);
        int := int + (nr - 3NIL_DATA.positions[pos]);

        mat := BLUEPRINT_MATS(8 - m);

        # based on 'IntBit' but putting values directly into matrix
        for i in [1 .. m] do
            for j in [1 .. i - 1] do
                rem := RemInt(int, 8 - m);
                int := (int - rem) / (8 - m);
                mat[9 - i][9 - j] := rem + 1;
            od;
            mat[9 - i][9 - i] := 3NIL_DATA.diag[m - i + 1];
            for j in [i + 1 .. m] do
                rem := RemInt(int, 8 - m);
                int := (int - rem) / (8 - m);
                mat[9 - i][9 - j] := rem + 1;
            od;
        od;

        return mat;
    fi;

    # set up list with first idempotent
    flatmat := EmptyPlist(size ^ 2);

    flatmat[1] := 1;
    if size = 8 then
      for i in [1 .. 7] do
        for k in [1 .. 8] do
          flatmat[1 + k + 9 * (i - 1)] :=
            INT_CHAR(data[k + 8 * (i - 1)][nr]) - 47;
        od;
        flatmat[1 + 9 * i] := diag[i + 1];
      od;
    else
      for i in [2 .. size ^ 2] do
        flatmat[i] := INT_CHAR(data[i - 1][nr]) - 47;
      od;
    fi;

    return ListToMatrix(flatmat);
end);

InstallGlobalFunction(SmallSemigroupCreator,
function(A)
  local elms, S;

  S := Objectify(SmallSemigroupType, rec(table := A));
  SetIsAssociative(S, true);
  SetSize(S, Length(A));

  elms := Immutable(List([1 .. Length(A)],
                         i -> Objectify(SmallSemigroupEltType,
                                        rec(index := i, semi := S))));

  SetIsSSortedList(elms, true);
  SetGeneratorsOfMagma(S, elms);
  SetAsSSortedList(S, elms);
  SetMultiplicationTable(S, A);

  return S;
end);

InstallGlobalFunction(SemigroupByMultiplicationTableNC,
function(A)
  A := MagmaByMultiplicationTable(A);
  SetIsAssociative(A, true);
  return A;
end);

InstallGlobalFunction(SmallSemigroup,
function(arg...)
  local size, nr;

  if Length(arg) = 2 and ForAll(arg, IsPosInt) then
    size := arg[1];
    nr := arg[2];
  elif Length(arg) = 1 and ForAll(arg[1], IsPosInt) then
    size := arg[1][1];
    nr := arg[1][2];
  else
    Error("the argument must be 2 positive integers or a",
          " list of 2 positive integers");
  fi;

  while size > 8 do;
    Error("semigroups of size ", size, " are not available, \n",
    "you can change the value of < size > and 'return;'\n");
  od;

  while nr > NrSmallSemigroups(size) do
    Error("there are only ",
          NrSmallSemigroups(size),
          " semigroups of size ",
          size,
          ", \nyou can change the value of <nr> and 'return;'\n");
  od;
  return SmallSemigroupNC(size, nr);
end);

InstallGlobalFunction(SmallSemigroupNC,
function(size, nr)
  local table, S;

  table := RecoverMultiplicationTableNC(size, nr);
  S := SmallSemigroupCreator(table);
  SetIdSmallSemigroup(S, [Size(S), nr]);
  return S;
end);

InstallGlobalFunction(UnloadSmallsemiData, function(uselater)
  local pos;

  # unbind data for semigroups sizes 2 to 7
  for pos in [1 .. 6] do
    Unbind(DATA2TO7[pos]);
  od;

  # unbind data for semigroups size 8 which are not 3 - nilpotent
  pos := PositionBound(DATA8);
  if pos <> fail then
    Unbind(DATA8[pos]);
  fi;

  # unbind data for semigroups size 8 which are 3 - nilpotent
  3NIL_DATA.diag := fail ;
  Unbind(3NIL_DATA.strlist);
  Unbind(3NIL_DATA.positions);
  Unbind(3NIL_DATA.next);

  # unbind data essential for the use of smallsemi
  if not uselater then

    # unbind data records from info files
    for pos in [1 .. 8] do
      Unbind(MOREDATA2TO8[pos]);
    od;

  fi;
end);

#############################################################################
# GLOBAL VARIABLES
#############################################################################

InstallFlushableValue(3NIL_DATA, rec(diag := fail));
InstallFlushableValue(DATA2TO7, []);
InstallFlushableValue(DATA8, []);

#############################################################################
# INTERNAL FUNCTIONS
#############################################################################

InstallGlobalFunction(BLUEPRINT_MATS, function(k)
  local mat, i;
  Assert(0, k in [2 .. 8]);

  # size 8 matrix
  mat := EmptyPlist(8);
  # first k zero rows (the zero is '1')
  for i in [1 .. k] do
    mat[i] := ListWithIdenticalEntries(8, 1);
  od;
  # zero columns (the zero is '1')
  for i in [k + 1 .. 8] do
    mat[i] := ListWithIdenticalEntries(k, 1);
  od;

  return mat;
end);

InstallGlobalFunction(READ_3NIL_DATA, function(diag)
  local diagstr, file, posdiffs, i;

  # set diagonal
  3NIL_DATA.diag := diag;
  diagstr := Concatenation(List(diag, String));

  # read cayle table data
  file := Filename(DirectoriesPackageLibrary("smallsemi", "data/data8-3nil"),
                                             Concatenation("diag",
                                                           diagstr,
                                                           ".gl"));
  3NIL_DATA.strlist := SplitString(StringFile(file), "\n");
  # remove copyright
  Remove(3NIL_DATA.strlist, 1);

  # read position differences information
  file := Filename(DirectoriesPackageLibrary("smallsemi", "data/data8-3nil"),
                                             Concatenation("diag",
                                                           diagstr,
                                                           "pos.gl"));
  posdiffs := SplitString(StringFile(file), "\n");
  posdiffs := List(posdiffs, Int);

  # create actual position list
  3NIL_DATA.positions := [posdiffs[1]];
  for i in [2 .. Length(posdiffs)] do
    3NIL_DATA.positions[i] := 3NIL_DATA.positions[i - 1] + posdiffs[i];
  od;

  # reset counter
  3NIL_DATA.next := 2;
end);

InstallGlobalFunction(READ_MOREDATA2TO8,
function()
  local dir, md, n, file, i, prop;
  dir := DirectoriesPackageLibrary("smallsemi", "data");

  Info(InfoSmallsemi, 1,
  "Smallsemi: loading data for semigroup properties. Please be patient.");

  md := [];

  for n in [1 .. 8] do
    file := Filename(dir, Concatenation("info", String(n), ".g"));
    if file <> fail then
      md[n] := EvalString(StringFile(file));
    else
      md[n] := rec();
    fi;
    for prop in Filtered(RecNames(md[n]), x -> IsUpperAlphaChar(x[1])) do
      # for position lists with more than one entry the first entry
      # and the differences are stored; recover actual position list
      if Length(md[n].(prop)) >= 2 then
        for i in [2 .. Length(md[n].(prop))] do
          md[n].(prop)[i] := md[n].(prop)[i - 1] + md[n].(prop)[i];
        od;
      fi;
    od;
  od;
  return md;
end);

############################################################################
# Methods for 'Small Semigroups'
############################################################################

InstallMethod(\=, "for two small semis", IsIdenticalObj,
[IsSmallSemigroup, IsSmallSemigroup], 10,
{x, y} -> IdSmallSemigroup(x) = IdSmallSemigroup(y));

InstallMethod(\<, "for two small semis", IsIdenticalObj,
[IsSmallSemigroup, IsSmallSemigroup],
{x, y} -> IdSmallSemigroup(x) < IdSmallSemigroup(y));

InstallMethod(Representative, "for a small semigroup", [IsSmallSemigroup],
x -> Elements(x)[1]);

InstallMethod(PrintObj, "for a small semigroup", [IsSmallSemigroup],
function(x)
  Print("<small semigroup of size ", Size(x), ">");
end);

InstallMethod(String, "for a small semigroup", [IsSmallSemigroup],
x -> Concatenation("<small semigroup of size ", String(Size(x)), ">"));

InstallMethod(ViewObj,  "for a small semigroup", [IsSmallSemigroup],
function(x)
  Print("<small semigroup of size ", Size(x), ">");
end);

############################################################################
# Methods for 'Small Semigroup Elements'
#############################################################################

InstallMethod(\=, "for two elements of a small semi",
IsIdenticalObj, [IsSmallSemigroupElt, IsSmallSemigroupElt],
{x, y} -> x!.index = y!.index and x!.semi = y!.semi);

InstallMethod(\<, "for two elements of a small semi",
IsIdenticalObj, [IsSmallSemigroupElt, IsSmallSemigroupElt],
{x, y} -> x!.index < y!.index and x!.semi = y!.semi);

InstallMethod(\*, "for two elements of a small semi",
IsIdenticalObj, [IsSmallSemigroupElt, IsSmallSemigroupElt],
function(x, y)
  local table;
  if x!.semi = y!.semi then
    table := x!.semi!.table;
    return AsList(x!.semi)[table[x!.index][y!.index]];
  fi;
  Error("cannot multiply elements from different semigroups in ",
        "'Smallsemi'");
end);

InstallOtherMethod(OneOp, "for a small semigroup elt",
[IsSmallSemigroupElt],
function(x)
  local table, pos;

  table := x!.semi!.table;
  pos := Position(table, [1 .. Length(table)]);

  if pos <> fail then
    if List(table, x -> x[pos]) = [1 .. Length(table)] then
      return AsList(x!.semi)[pos];
    fi;
  fi;

  return fail;
end);

InstallMethod(PrintObj, "for a small semigroup elt", [IsSmallSemigroupElt],
function(x)
  Print("s", x!.index);
end);

InstallMethod(String,  "for a small semigroup elt", [IsSmallSemigroupElt],
x -> Concatenation("s", String(x!.index)));

InstallMethod(ViewObj,  "for a small semigroup elt", [IsSmallSemigroupElt],
function(x)
  Print("s", x!.index);
end);

InstallMethod(ViewString,  "for a small semigroup elt", [IsSmallSemigroupElt],
x -> Concatenation("s", String(x!.index)));

Quelle small.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.51 Sekunden (vorverarbeitet) ]