Quelle  cong.gi   Sprache: unbekannt

############################################################################
##
##  congruences/cong.gi
##  Copyright (C) 2015-2022                               Michael C. Young
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##
## This file contains some general functions, operations and attributes of
## semigroup congruences.  Methods for specific types of congruence are
## implemented in the following files:
##
##       conginv.gi     - Inverse semigroups
##       congpairs.gi   - Congruences with generating pairs
##       congrees.gi    - Rees congruences
##       congrms.gi     - (0-)simple Rees matrix semigroups
##       congsimple.gi  - (0-)simple semigroups
##       conguniv.gi    - Universal congruences
##
## cong.gd contains declarations for many of these.
##

# This file contains implementations of methods for congruences that don't
# assume any particular representation.

########################################################################
# 0. Categories
########################################################################

InstallMethod(CongruenceHandednessString, "for a right congruence",
[IsRightMagmaCongruence and IsRightSemigroupCongruence], C -> "right");

InstallMethod(CongruenceHandednessString, "for a left congruence",
[IsLeftMagmaCongruence and IsLeftSemigroupCongruence], C -> "left");

InstallMethod(CongruenceHandednessString, "for a 2-sided congruence",
[IsMagmaCongruence and IsSemigroupCongruence], C -> "2-sided");

# This is required for QuotientSemigroups and their subsemigroups.
InstallImmediateMethod(CanEasilyCompareElements,
IsCongruenceClass and HasEquivalenceClassRelation, 0,
C -> CanUseLibsemigroupsCongruence(EquivalenceClassRelation(C)));

########################################################################
# Flexible functions for creating congruences
########################################################################

InstallGlobalFunction(SemigroupCongruence,
function(arg...)
  local S, opts, s_opts, x, pairs, cong;
  if not Length(arg) >= 2 then
    ErrorNoReturn("at least 2 arguments are required");
  elif not IsSemigroup(arg[1]) then
    ErrorNoReturn("the 1st argument is not a semigroup");
  fi;
  S := arg[1];

  # Set up any options
  if IsRecord(Last(arg)) then
    opts := Last(arg);
    arg := arg{[1 .. Length(arg) - 1]};
  else
    opts := rec();
  fi;
  s_opts := SEMIGROUPS.OptionsRec(S);
  for x in RecNames(s_opts) do
    if not IsBound(opts.(x)) then
      opts.(x) := s_opts.(x);
    fi;
  od;

  if IsHomogeneousList(arg[2]) then
    # We should have a list of generating pairs
    if Length(arg) = 2 then
      pairs := arg[2];
      if not IsEmpty(pairs) then
        if (not IsList(pairs[1])) or IsMatrixObj(pairs[1]) then
          pairs := [pairs];
        fi;
      fi;
    elif Length(arg) > 2 then
      pairs := arg{[2 .. Length(arg)]};
    fi;
    if not ForAll(pairs, p -> Size(p) = 2) then
      ErrorNoReturn("the 2nd argument (a list of lists) contains lists ",
                    "of size not equal to 2");
    elif not ForAll(pairs, p -> p[1] in S and p[2] in S) then
      ErrorNoReturn("the 2nd argument (a list of lists) contains items ",
                    "that do not belong to the 1st argument (a semigroup)");
    fi;

    # Remove any reflexive pairs
    pairs := Filtered(pairs, p -> p[1] <> p[2]);

    # Decide which representation to use
    if not IsFinite(S)
        or ((HasIsSimpleSemigroup(S) or IsActingSemigroup(S)
           or HasSize(S) or IsReesMatrixSemigroup(S))
          and IsSimpleSemigroup(S)) or
         ((HasIsZeroSimpleSemigroup(S) or IsActingSemigroup(S)
           or HasSize(S) or IsReesZeroMatrixSemigroup(S))
          and IsZeroSimpleSemigroup(S)) then
      return SemigroupCongruenceByGeneratingPairs(S, pairs);
    elif IsInverseSemigroup(S) and IsGeneratorsOfInverseSemigroup(S) and
         Size(S) >= opts.cong_by_ker_trace_threshold then
      cong := SemigroupCongruenceByGeneratingPairs(S, pairs);
      cong := AsInverseSemigroupCongruenceByKernelTrace(cong);
      SetGeneratingPairsOfMagmaCongruence(cong, pairs);
      return cong;
    else
      return SemigroupCongruenceByGeneratingPairs(S, pairs);
    fi;
  elif IsGeneralMapping(arg[2]) and
      ((IsRMSCongruenceByLinkedTriple(arg[3]) and IsSimpleSemigroup(S))
       or (IsRZMSCongruenceByLinkedTriple(arg[3]) and IsZeroSimpleSemigroup(S)))
      then
    # We should have a congruence of an isomorphic RMS/RZMS
    if Range(arg[2]) = Range(arg[3]) and S = Source(arg[2]) then
      return CongruenceByIsomorphism(arg[2], arg[3]);
    else
      ErrorNoReturn("the range of the 3rd argument (a congruence) is ",
                    "not a Rees (0-)matrix semigroup isomorphic to the ",
                    "1st argument");
    fi;
  elif HasIsSemigroupIdeal(arg[2])
      and IsSemigroupIdeal(arg[2])
      and Parent(arg[2]) = S then
    return ReesCongruenceOfSemigroupIdeal(arg[2]);
  elif Length(arg) = 3
      and IsInverseSemigroup(arg[2])
      and IsGeneratorsOfInverseSemigroup(arg[2])
      and IsDenseList(arg[3])
      and IsInverseSemigroup(S)
      and IsGeneratorsOfInverseSemigroup(S) then
    # We should have the kernel and trace of a congruence on an inverse
    # semigroup
    return InverseSemigroupCongruenceByKernelTrace(S, arg[2], arg[3]);
  fi;
  ErrorNoReturn("the arguments are not valid for this function");
end);

BindGlobal("_LeftOrRightCong",
function(CongruenceConstructor, arg)
  local S, pairs;
  if not Length(arg) >= 2 then
    ErrorNoReturn("at least 2 arguments are required");
  elif not IsSemigroup(arg[1]) then
    ErrorNoReturn("the 1st argument is not a semigroup");
  fi;
  S := arg[1];

  if IsHomogeneousList(arg[2]) then
    # We should have a list of generating pairs
    if Length(arg) = 2 then
      pairs := arg[2];
      if not IsEmpty(pairs) and not IsList(pairs[1]) then
        pairs := [pairs];
      fi;
    elif Length(arg) > 2 then
      pairs := arg{[2 .. Length(arg)]};
    fi;
    if not ForAll(pairs, p -> Size(p) = 2) then
      ErrorNoReturn("the 2nd argument (a list of lists) contains lists ",
                    "of size not equal to 2");
    elif not ForAll(pairs, p -> p[1] in S and p[2] in S) then
      ErrorNoReturn("the 2nd argument (a list of lists) contains items ",
                    "that do not belong to the 1st argument (a semigroup)");
    fi;
    # Remove any reflexive pairs
    pairs := Filtered(pairs, p -> p[1] <> p[2]);
    return CongruenceConstructor(S, pairs);
  else
    ErrorNoReturn("the arguments are not valid for this function");
  fi;
end);

InstallGlobalFunction(LeftSemigroupCongruence,
# Can't be a lambda because arg has a special meaning here
function(arg...)
  return _LeftOrRightCong(LeftSemigroupCongruenceByGeneratingPairs, arg);
end);

InstallGlobalFunction(RightSemigroupCongruence,
# Can't be a lambda because arg has a special meaning here
function(arg...)
  return _LeftOrRightCong(RightSemigroupCongruenceByGeneratingPairs, arg);
end);

########################################################################
# Trivial congruence
########################################################################

InstallMethod(TrivialCongruence, "for a semigroup",
[IsSemigroup], S -> SemigroupCongruence(S, []));

########################################################################
# Congruence operators
########################################################################

InstallMethod(IsSuperrelation, "for semigroup congruences",
[IsLeftRightOrTwoSidedCongruence, IsLeftRightOrTwoSidedCongruence],
{lhop, rhop} -> IsSubrelation(rhop, lhop));

########################################################################
# Congruence classes
########################################################################

InstallMethod(EquivalenceClassOfElement,
"for a left, right, or 2-sided semigroup congruence and mult. elt.",
[IsLeftRightOrTwoSidedCongruence, IsMultiplicativeElement],
function(C, x)
  if not x in Range(C) then
    ErrorNoReturn("the 2nd argument (a mult. elt.) does not belong ",
                  "to the range of the 1st argument (a ",
                  CongruenceHandednessString(C),
                  " congruence)");
  fi;
  return EquivalenceClassOfElementNC(C, x);
end);

InstallMethod(EquivalenceClassOfElementNC,
"for a left, right, or 2-sided congruence and mult. elt.",
[IsLeftRightOrTwoSidedCongruence, IsMultiplicativeElement],
function(C, x)
  local filt, class;
  if IsMagmaCongruence(C) then
    # IsCongruenceClass is declared in the GAP library and it does not belong
    # to IsAttributeStoringRep
    filt := IsCongruenceClass and IsAttributeStoringRep;
  elif IsLeftMagmaCongruence(C) then
    # IsLeftCongruenceClass is declared in the Semigroups pkg and does belong
    # to IsAttributeStoringRep
    filt := IsLeftCongruenceClass;
  else
    Assert(1, IsRightMagmaCongruence(C));
    filt := IsRightCongruenceClass;
  fi;

  class := Objectify(NewType(FamilyObj(Range(C)), filt), rec());
  SetParentAttr(class, Range(C));
  SetEquivalenceClassRelation(class, C);
  SetRepresentative(class, x);
  if HasIsFinite(Range(C)) and IsFinite(Range(C)) then
    SetIsFinite(class, true);
  fi;

  return class;
end);

########################################################################
# Congruence class attributes
########################################################################

# Maybe these should only be for CanComputeEquivalenceRelationPartition?

InstallMethod(AsList,
"for a class of a left, right, or 2-sided semigroup congruence",
[IsLeftRightOrTwoSidedCongruenceClass],
C -> ImagesElm(EquivalenceClassRelation(C), Representative(C)));

InstallMethod(Enumerator,
"for a class of a left, right, or 2-sided semigroup congruence",
[IsLeftRightOrTwoSidedCongruenceClass],
6,  # To beat the library method for magma congruence classes
AsList);

InstallMethod(Size,
"for a class of a left, right, or 2-sided semigroup congruence",
[IsLeftRightOrTwoSidedCongruenceClass],
C -> Size(AsList(C)));

########################################################################
# Congruence class operators
########################################################################

# Multiplication for congruence classes: only makes sense for 2-sided
InstallMethod(\*, "for two congruence classes",
[IsCongruenceClass, IsCongruenceClass],
function(lhop, rhop)
  if EquivalenceClassRelation(lhop) <> EquivalenceClassRelation(rhop) then
    ErrorNoReturn("the arguments (cong. classes) are not classes of the same ",
                  "congruence");
  fi;
  return EquivalenceClassOfElementNC(EquivalenceClassRelation(lhop),
                                     Representative(lhop) *
                                     Representative(rhop));
end);

InstallMethod(\=,
"for classes of a left, right, or 2-sided semigroup congruence",
IsIdenticalObj,
[IsLeftRightOrTwoSidedCongruenceClass, IsLeftRightOrTwoSidedCongruenceClass],
function(lhop, rhop)
  return EquivalenceClassRelation(lhop) = EquivalenceClassRelation(rhop)
    and [Representative(lhop), Representative(rhop)]
    in EquivalenceClassRelation(lhop);
end);

InstallMethod(\in,
"for a mult. elt. and a class of a left, right or 2-sided congruence",
[IsMultiplicativeElement, IsLeftRightOrTwoSidedCongruenceClass],
3,  # to beat the library method
function(x, class)
  local C;
  C := EquivalenceClassRelation(class);
  return x in Range(C) and [x, Representative(class)] in C;
end);

InstallMethod(ViewObj,
"for a left, right, or 2-sided congruence class",
[IsLeftRightOrTwoSidedCongruenceClass],
function(C)
  local string;
  string := CongruenceHandednessString(EquivalenceClassRelation(C));
  Print("<", string, " congruence class of ");
  ViewObj(Representative(C));
  Print(">");
end);

########################################################################
# Congruence class actions
########################################################################

InstallMethod(OnLeftCongruenceClasses,
"for a left congruence class and a multiplicative element",
[IsLeftRightOrTwoSidedCongruenceClass, IsMultiplicativeElement],
function(class, x)
  local C;
  # This is necessary because IsCongruenceClass is not a sub-category of
  # IsLeftCongruenceClass or IsRightCongruenceClass
  if IsRightCongruenceClass(class) then
    TryNextMethod();
  fi;
  C := EquivalenceClassRelation(class);
  return EquivalenceClassOfElementNC(C, x * Representative(class));
end);

InstallMethod(OnRightCongruenceClasses,
"for a right congruence class and a multiplicative element",
[IsLeftRightOrTwoSidedCongruenceClass, IsMultiplicativeElement],
function(class, x)
  local C;
  # This is necessary because IsCongruenceClass is not a sub-category of
  # IsLeftCongruenceClass or IsRightCongruenceClass
  if IsLeftCongruenceClass(class) then
    TryNextMethod();
  fi;
  C := EquivalenceClassRelation(class);
  return EquivalenceClassOfElementNC(C, Representative(class) * x);
end);

[ Dauer der Verarbeitung: 0.31 Sekunden  (vorverarbeitet)  ]