Gedichte Musik Bilder Quellcodebibliothek Diashow Normaldarstellung
Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/gap/main/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 29.7.2025 mit Größe 12 kB image not shown  

Quelle  lambda-rho.gi   Sprache: unbekannt

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

InstallMethod(LambdaOrb, "for an acting semigroup with generators",
[IsActingSemigroup and HasGeneratorsOfSemigroup],
function(S)
  local record, gens, o;

  record := ShallowCopy(LambdaOrbOpts(S));

  record.schreier     := true;
  record.orbitgraph   := true;
  record.storenumbers := true;
  record.log          := true;
  record.parent       := S;
  record.treehashsize := SEMIGROUPS.OptionsRec(S).hashlen;

  gens := List(GeneratorsOfSemigroup(S), x -> ConvertToInternalElement(S, x));

  record.scc_reps := [FakeOne(gens)];

  o := Orb(gens, LambdaOrbSeed(S), LambdaAct(S), record);

  SetFilterObj(o, IsLambdaOrb);

  if IsInverseActingSemigroupRep(S) then
    SetFilterObj(o, IsInverseOrb);
  fi;

  return o;
end);

InstallGlobalFunction(LambdaOrbMults,
function(o, m)
  local scc, gens, one, mults, genpos, inv, trace, i;

  scc := OrbSCC(o);

  if IsBound(o!.hasmults) then
    if IsBound(o!.hasmults[m]) and o!.hasmults[m] then
      return o!.mults;
    fi;
  else
    if not IsBound(o!.mults) then
      o!.mults := EmptyPlist(Length(o));
    fi;
    o!.hasmults := BlistList([1 .. Length(scc)], []);
  fi;

  o!.hasmults[m] := true;
  scc := OrbSCC(o)[m];
  gens := o!.gens;
  one := FakeOne(gens);
  mults := o!.mults;

  # it would be better to use the SchreierTree here not the ReverseSchreierTree
  # and shouldn't there be a second case of inverse orbits here??
  genpos := ReverseSchreierTreeOfSCC(o, m);
  trace := function(i)
    local x;
    if IsBound(mults[i]) then
      return mults[i][2];
    elif i = scc[1] then
      mults[i] := [one, one];
      return one;
    fi;
    x := gens[genpos[1][i]] * trace(genpos[2][i]);
    mults[i] := [inv(o[i], x), x];
    return x;
  end;
  inv := {lambda, x} -> LambdaInverse(o!.parent)(lambda, x);

  for i in scc do
    trace(i);
  od;
  return o!.mults;
end);

# f takes o[i] to o[scc[1]] and inv(o[i], f) takes o[scc[1]] to o[i]
# JDM: this should be the other way around like in RhoOrbMult, and using
# SchreierTreeOfSCC instead of its reverse.

InstallGlobalFunction(LambdaOrbMult,
function(o, m, i)
  local scc, mults, gens, one, genpos, inv, trace;

  if IsBound(o!.mults) then
    if IsBound(o!.mults[i]) then
      return o!.mults[i];
    fi;
  else
    o!.mults := EmptyPlist(Length(o));
  fi;

  scc := OrbSCC(o)[m];
  gens := o!.gens;
  one := FakeOne(gens);
  mults := o!.mults;

  if not IsInverseActingSemigroupRep(o!.parent) then
    # It would be better to use the SchreierTree here not the
    # ReverseSchreierTree
    genpos := ReverseSchreierTreeOfSCC(o, m);
    inv := LambdaInverse(o!.parent);

    trace := function(i)  # gaplint: disable=W047
      local x;
      if IsBound(mults[i]) then
        return mults[i][2];
      elif i = scc[1] then
        mults[i] := [one, one];
        return one;
      fi;
      x := gens[genpos[1][i]] * trace(genpos[2][i]);
      mults[i] := [inv(o[i], x), x];
      return x;
    end;
  else
    genpos := SchreierTreeOfSCC(o, m);

    trace := function(i)
      local x;
      if IsBound(mults[i]) then
        return mults[i][2];
      elif i = scc[1] then
        mults[i] := [one, one];
        return one;
      fi;
      x := InverseMutable(gens[genpos[1][i]]) * trace(genpos[2][i]);
      mults[i] := [InverseMutable(x), x];
      return x;
    end;
  fi;

  trace(i);
  return o!.mults[i];
end);

# JDM this is really slow (due to EvaluateWord) for large degree

InstallGlobalFunction(LambdaOrbRep,
function(o, m)
  local w;

  if IsBound(o!.scc_reps[m]) then
    return o!.scc_reps[m];
  fi;

  w := TraceSchreierTreeForward(o, OrbSCC(o)[m][1]);
  o!.scc_reps[m] := EvaluateWord(o, w);

  if not IsIdealOrb(o) then
    o!.scc_reps[m] := o!.scc_reps[1] * o!.scc_reps[m];
  fi;

  return o!.scc_reps[m];
end);

InstallGlobalFunction(RhoOrbRep,
function(o, m)
  local w;

  if IsBound(o!.scc_reps[m]) then
    return o!.scc_reps[m];
  fi;

  w := TraceSchreierTreeForward(o, OrbSCC(o)[m][1]);
  o!.scc_reps[m] := EvaluateWord(o, Reversed(w));

  if not IsIdealOrb(o) then
    o!.scc_reps[m] := o!.scc_reps[m] * o!.scc_reps[1];
  fi;

  return o!.scc_reps[m];
end);

InstallGlobalFunction(LambdaOrbSchutzGp,
function(o, m)
  local s, gens, scc, lookup, orbitgraph, genstoapply, lambdaperm, rep, rank,
  one, bound, g, stop, forward, f, k, l;

  if IsBound(o!.schutz) then
    if IsBound(o!.schutz[m]) then
      return o!.schutz[m];
    fi;
  else
    o!.schutz := EmptyPlist(Length(OrbSCC(o)));
    o!.schutzstab := EmptyPlist(Length(OrbSCC(o)));
  fi;

  s := o!.parent;
  gens := o!.gens;
  scc := OrbSCC(o)[m];
  lookup := o!.scc_lookup;
  orbitgraph := OrbitGraph(o);
  genstoapply := [1 .. Length(gens)];
  lambdaperm := LambdaPerm(s);
  rep := LambdaOrbRep(o, m);
  rank := LambdaRank(s)(o[scc[1]]);
  one := LambdaIdentity(s)(rank);
  bound := LambdaBound(s)(rank);

  g := Group(one);

  stop := false;

  for k in scc do
    forward := LambdaOrbMult(o, m, k)[1];
    for l in genstoapply do
      if IsBound(orbitgraph[k][l]) and lookup[orbitgraph[k][l]] = m then
        f := lambdaperm(rep, rep * forward * gens[l]
                             * LambdaOrbMult(o, m, orbitgraph[k][l])[2]);
        g := ClosureGroup(g, f);
      fi;

      if Size(g) >= bound then
        stop := true;
        break;
      fi;
    od;
    if stop then
      break;
    fi;
  od;

  o!.schutz[m] := g;

  if stop then
    o!.schutzstab[m] := true;
  elif Size(g) = 1 then
    o!.schutzstab[m] := false;
  elif IsPermGroup(g) then
    o!.schutzstab[m] := StabChainImmutable(g);
  else  # if IsMatrixGroup(g)
    o!.schutzstab[m] := g;
  fi;

  return g;
end);

InstallMethod(RhoOrbStabChain, "for a rho orb and scc index",
[IsOrbit, IsPosInt],
function(o, m)

  if IsBound(o!.schutzstab) then
    if IsBound(o!.schutzstab[m]) then
      return o!.schutzstab[m];
    fi;
  fi;

  RhoOrbSchutzGp(o, m);
  return o!.schutzstab[m];
end);

InstallGlobalFunction(LambdaOrbStabChain,
function(o, m)

  if IsBound(o!.schutzstab) then
    if IsBound(o!.schutzstab[m]) then
      return o!.schutzstab[m];
    fi;
  fi;

  LambdaOrbSchutzGp(o, m);
  return o!.schutzstab[m];
end);

InstallMethod(RhoOrb, "for an acting semigroup with generators",
[IsActingSemigroup and HasGeneratorsOfSemigroup],
function(S)
  local record, gens, o;

  record := ShallowCopy(RhoOrbOpts(S));
  record.schreier := true;
  record.orbitgraph := true;
  record.storenumbers := true;
  record.log := true;
  record.parent := S;
  record.treehashsize := SEMIGROUPS.OptionsRec(S).hashlen;

  gens := List(GeneratorsOfSemigroup(S), x -> ConvertToInternalElement(S, x));

  record.scc_reps := [FakeOne(gens)];

  o := Orb(gens, RhoOrbSeed(S), RhoAct(S), record);

  SetFilterObj(o, IsRhoOrb);

  if IsInverseActingSemigroupRep(S) then
    SetFilterObj(o, IsInverseOrb);
  fi;
  return o;
end);

# f takes o[scc[1]] to o[i] and inv(o[scc[1]],f) takes o[i] to o[scc[1]]

InstallGlobalFunction(RhoOrbMult,
function(o, m, i)
  local scc, gens, one, mults, genpos, inv, trace;

  if IsBound(o!.mults) then
    if IsBound(o!.mults[i]) then
      return o!.mults[i];
    fi;
  else
    o!.mults := EmptyPlist(Length(o));
  fi;

  scc := OrbSCC(o)[m];
  gens := o!.gens;
  one := FakeOne(gens);

  mults := o!.mults;

  genpos := SchreierTreeOfSCC(o, m);
  inv := x -> RhoInverse(o!.parent)(o[scc[1]], x);

  trace := function(i)
    local x;
    if IsBound(mults[i]) then
      return mults[i][1];
    elif i = scc[1] then
      mults[i] := [one, one];
      return one;
    fi;
    x := gens[genpos[1][i]] * trace(genpos[2][i]);
    mults[i] := [x, inv(x)];
    return x;
  end;

  trace(i);
  return o!.mults[i];
end);

# f takes o[scc[1]] to o[i] and inv(o[i], f) takes o[i] to o[scc[1]]

InstallGlobalFunction(RhoOrbMults,
function(o, m)
  local scc, gens, one, mults, genpos, inv, trace, i;

  scc := OrbSCC(o);
  if IsBound(o!.hasmults) then
    if IsBound(o!.hasmults[m]) and o!.hasmults[m] then
      return o!.mults;
    fi;
  else
    if not IsBound(o!.mults) then
      o!.mults := EmptyPlist(Length(o));
    fi;
    o!.hasmults := BlistList([1 .. Length(scc)], []);
  fi;

  o!.hasmults[m] := true;
  scc := OrbSCC(o)[m];
  gens := o!.gens;
  one := FakeOne(gens);
  mults := o!.mults;

  genpos := SchreierTreeOfSCC(o, m);
  inv := x -> RhoInverse(o!.parent)(o[scc[1]], x);

  trace := function(i)  # gaplint: disable=W047
    local x;
    if IsBound(mults[i]) then
      return mults[i][1];
    elif i = scc[1] then
      mults[i] := [one, one];
      return one;
    fi;
    x := gens[genpos[1][i]] * trace(genpos[2][i]);
    mults[i] := [x, inv(x)];
    return x;
  end;

  for i in scc do
    trace(i);
  od;
  return o!.mults;
end);

InstallGlobalFunction(RhoOrbSchutzGp,
function(o, m)
  local S, rank, bound, one, G, gens, nrgens, scc, lookup, orbitgraph,
   lambdaperm, rep, mults, stop, i, j;

  if IsBound(o!.schutz) then
    if IsBound(o!.schutz[m]) then
      return o!.schutz[m];
    fi;
  else
    o!.schutz := EmptyPlist(Length(OrbSCC(o)));
    o!.schutzstab := EmptyPlist(Length(OrbSCC(o)));
  fi;

  S := o!.parent;
  scc := OrbSCC(o)[m];
  rank := RhoRank(S)(o[scc[1]]);
  bound := RhoBound(S)(rank);
  one := RhoIdentity(S)(rank);
  G := Group(one);

  if bound = 1 or rank = 0 then
    o!.schutz[m] := G;
    o!.schutzstab[m] := false;
    return G;
  fi;

  gens := o!.gens;
  nrgens := Length(gens);
  lookup := o!.scc_lookup;
  orbitgraph := OrbitGraph(o);
  lambdaperm := LambdaPerm(S);
  rep := RhoOrbRep(o, m);
  mults := RhoOrbMults(o, m);

  stop := false;

  for i in scc do
    for j in [1 .. nrgens] do
      if IsBound(orbitgraph[i][j]) and lookup[orbitgraph[i][j]] = m then
        G := ClosureGroup(G, lambdaperm(rep,
                                        mults[orbitgraph[i][j]][2] * gens[j] *
                                        mults[i][1] * rep));
        if Size(G) >= bound then
          stop := true;
          break;
        fi;
      fi;
    od;
    if stop then
        break;
    fi;
  od;
  o!.schutz[m] := G;

  if stop then
    o!.schutzstab[m] := true;
  elif Size(G) = 1 then
    o!.schutzstab[m] := false;
  elif IsPermGroup(G) then
    o!.schutzstab[m] := StabChainImmutable(G);
  else  # if IsMatrixGroup(g)
    o!.schutzstab[m] := G;
  fi;
  return G;
end);

InstallMethod(RelativeLambdaOrb,
"for acting semigroup and subsemigroup",
[IsActingSemigroup, IsActingSemigroup],
function(S, T)
  local o, D, act, schreiergen, schreierpos, genstoapply, gens, x, pos, i, j,
  m;

  if not IsSubsemigroup(S, T) then
    ErrorNoReturn("the 2nd argument (an acting semigroup) must be ",
                  "a subsemigroup of the 1st argument (an acting semigroup)");
  fi;
  Info(InfoSemigroups, 1, "Computing relative lambda orb . . ");

  o   := StructuralCopy(Enumerate(LambdaOrb(S)));
  o!.scc_reps := [FakeOne(GeneratorsOfSemigroup(S))];

  Unbind(o!.scc);
  Unbind(o!.trees);
  Unbind(o!.scc_lookup);
  Unbind(o!.mults);
  Unbind(o!.schutz);
  Unbind(o!.reverse);
  Unbind(o!.rev);
  Unbind(o!.schutzstab);
  Unbind(o!.factorgroups);
  Unbind(o!.factors);

  D   := List([1 .. Length(o)], x -> []);
  act := LambdaAct(S);
  schreiergen := ListWithIdenticalEntries(Length(o), fail);
  schreierpos := ListWithIdenticalEntries(Length(o), fail);
  genstoapply := [1 .. Length(GeneratorsOfSemigroup(T))];
  gens := GeneratorsOfSemigroup(T);

  for i in [1 .. Length(o)] do
    x := o[i];
    for j in genstoapply do
      pos := Position(o, act(x, gens[j]));
      Add(D[i], pos);
      if i < pos and schreiergen[pos] = fail then
        schreiergen[pos] := j;
        schreierpos[pos] := i;
      fi;
    od;
  od;
  o!.orbitgraph := D;
  # Compute scc wrt to the new orbit graph, but scc reps using the old Schreier
  # tree.
  for m in [2 .. Length(OrbSCC(o))] do
    LambdaOrbRep(o, m);
  od;

  o!.gens        := GeneratorsOfSemigroup(T);
  o!.schreierpos := schreierpos;
  o!.schreiergen := schreiergen;
  Info(InfoSemigroups,
       1,
       StringFormatted("found {} lambda values!", Length(o)));
  return o;
end);

[ Dauer der Verarbeitung: 0.26 Sekunden  (vorverarbeitet)  ]