GAP (Semigroups) - Chapter 9: Ideals

In this chapter we describe the various ways that an ideal of a semigroup can be created and manipulated in Semigroups.

The methods in the Semigroups package apply to any ideal of a semigroup that is created using the function SemigroupIdeal (9.1-1) or SemigroupIdealByGenerators. Anything that can be calculated for a semigroup defined by a generating set can also be found for an ideal. This works particularly well for regular ideals, since such an ideal can be represented using a similar data structure to that used to represent a semigroup defined by a generating set but without the necessity to find a generating set for the ideal. Many methods for non-regular ideals rely on first finding a generating set for the ideal, which can be costly (but not nearly as costly as an exhaustive enumeration of the elements of the ideal). We plan to improve the functionality of Semigroups for non-regular ideals in the future.

9.1 Creating ideals

9.1-1 SemigroupIdeal

If obj1, obj2, .. . are (any combination) of elements of the semigroup S or collections of elements of S (including subsemigroups and ideals of S), then SemigroupIdeal returns the 2-sided ideal of the semigroup S generated by the union of obj1, obj2, .. ..

gap> S := SymmetricInverseMonoid(10);
<symmetric inverse monoid of degree 10>
gap> I := SemigroupIdeal(S, PartialPerm([1, 2]));
<inverse partial perm semigroup ideal of rank 10 with 1 generator>
gap> Size(I);
4151
gap> I := SemigroupIdeal(S, I, Idempotents(S));
<inverse partial perm semigroup ideal of rank 10 with 1025 generators>

9.1-2 Ideals

If S is a finite non-empty semigroup, then this attribute returns a list of the non-empty two-sided ideals of S.

The ideals are returned in no particular order, and each ideal uses the minimum possible number of generators (see GeneratorsOfSemigroupIdeal (9.2-1)).

gap> S := Semigroup([Transformation([4, 3, 4, 1]),
>                    Transformation([4, 3, 2, 2])]);
<transformation semigroup of degree 4 with 2 generators>
gap> Ideals(S);
[ <non-regular transformation semigroup ideal of degree 4 with
      1 generator>,
 <non-regular transformation semigroup ideal of degree 4 with
     1 generator>,
<non-regular transformation semigroup ideal of degree 4 with
    2 generators>,
<regular transformation semigroup ideal of degree 4 with 1 generator>,
<non-regular transformation semigroup ideal of degree 4 with
  1 generator>,
<regular transformation semigroup ideal of degree 4 with 1 generator>
]

9.2 Attributes of ideals

9.2-1 GeneratorsOfSemigroupIdeal

This function returns the generators of the two-sided ideal I, which were used to defined I when it was created.

If I is an ideal of a semigroup, then I is defined to be the least 2-sided ideal of a semigroup S containing a set J of elements of S. The set J is said to generate I.

The notion of the generators of an ideal is distinct from the notion of the generators of a semigroup or monoid. In particular, the semigroup generated by the generators of an ideal is not, in general, equal to that ideal. Use GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup) to obtain a semigroup generating set for an ideal, but beware that this can be very costly.

gap> S := Semigroup(
> Bipartition([[1, 2, 3, 4, -1], [-2, -4], [-3]]),
> Bipartition([[1, 2, 3, -3], [4], [-1], [-2, -4]]),
> Bipartition([[1, 3, -2], [2, 4], [-1, -3, -4]]),
> Bipartition([[1], [2, 3, 4], [-1, -3, -4], [-2]]),
> Bipartition([[1], [2, 4, -2], [3, -4], [-1], [-3]]));;
gap> I := SemigroupIdeal(S, S.1 * S.2 * S.5);;
gap> GeneratorsOfSemigroupIdeal(I);
[ <bipartition: [ 1, 2, 3, 4, -4 ], [ -1 ], [ -2 ], [ -3 ]> ]
gap> I = Semigroup(GeneratorsOfSemigroupIdeal(I));
false

9.2-2 MinimalIdealGeneratingSet

This function returns a minimal set of elements of the parent of the semigroup ideal I required to generate I as an ideal.

gap> S := Monoid([
> Bipartition([[1, 2, 3, -2], [4], [-1, -4], [-3]]),
> Bipartition([[1, 4, -2, -4], [2, -1, -3], [3]])]);;
gap> I := SemigroupIdeal(S, S);;
gap> MinimalIdealGeneratingSet(I);
[ <block bijection: [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ]> ]

9.2-3 SupersemigroupOfIdeal

The Parent (Reference: Parent) of an ideal is the semigroup in which the ideal was created, i.e. the first argument of SemigroupIdeal (9.1-1) or SemigroupIdealByGenerators. This function returns the semigroup containing the generators of the semigroup (i.e. GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup)) which are used to compute the ideal.

For a regular semigroup ideal, SupersemigroupOfIdeal will always be the top most semigroup used to create any of the predecessors of the current ideal. For example, if S is a semigroup, I is a regular ideal of S, and J is an ideal of I, then Parent(J) is I and SupersemigroupOfIdeal(J) is S. This is to avoid computing a generating set for I, in this example, which is expensive and unnecessary since I is regular (in which case the Green's relations of I are just restrictions of the Green's relations on S).

If S is a semigroup, I is a non-regular ideal of S, J is an ideal of I, then SupersemigroupOfIdeal(J) is I, since we currently have to use GeneratorsOfSemigroup(I) to compute anything about I other than its size and membership.

gap> S := FullTransformationSemigroup(8);
<full transformation monoid of degree 8>
gap> x := Transformation([2, 6, 7, 2, 6, 1, 1, 5]);;
gap> D := DClass(S, x);
<Green's D-class: Transformation( [ 2, 6, 7, 2, 6, 1, 1, 5 ] )>
gap> R := PrincipalFactor(D);
<Rees 0-matrix semigroup 1050x56 over Group([ (2,8,7,4,3), (3,4) ])>
gap> S := Semigroup(List([1 .. 10], x -> Random(R)));
<subsemigroup of 1050x56 Rees 0-matrix semigroup with 10 generators>
gap> I := SemigroupIdeal(S, MultiplicativeZero(S));
<regular Rees 0-matrix semigroup ideal with 1 generator>
gap> SupersemigroupOfIdeal(I);
<subsemigroup of 1050x56 Rees 0-matrix semigroup with 10 generators>
gap> J := SemigroupIdeal(I, Representative(MinimalDClass(S)));
<regular Rees 0-matrix semigroup ideal with 1 generator>
gap> Parent(J) = I;
true
gap> SupersemigroupOfIdeal(J) = I;
false