Quelle  tfmnr.tex

%
\Chapter{Transformation nearrings}
%

In the previous chapter we introduced mappings on groups, and we
called them *endomappings*.  We also introduced the operation of
pointwise addition `+' for endomappings. Now we are able to use these
mappings together with pointwise addition `+' and composition `\*' to
construct left nearrings. These nearrings satisfy the distributive
law $x * (y + z) = x * y + x * z$.

A *transformation nearring* is a set of mappings on a group $G$ that
is closed under pointwise addition of mappings, under forming the
additive inverse and under functional composition. For more
information we suggest \cite{Pilz:Nearrings}, \cite{meldrum85:NATLWG},
and \cite{Clay:Nearrings},

The algorithms used can be found in
\cite{aichingereckernoebauer00:TUOCINT} and \cite{aichingerea00:CWN}.

The elements of a transformation nearring are given as endomappings on
the group $G$ (cf. Chapter ``Functions on groups that are not
necessarily homomorphisms: EndoMappings'').


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Constructing transformation nearrings}


\>TransformationNearRingByGenerators( <G>, <endomaplist> )

For a (possibly empty) list <endomaplist> of endomappings on a group
<G>, the constructor function `TransformationNearRingByGenerators' returns the
nearring  generated by these mappings. All of them must be
endomappings on the group <G>.

\beginexample
    gap> g := AlternatingGroup ( 4 );
    Alt( [ 1 .. 4 ] )
    gap> AsSortedList ( g );
    [ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), 
      (1,3,4), (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]
    gap> t := EndoMappingByPositionList ( g, [1,3,4,5,2,1,1,1,1,1,1,1] );
    <mapping: AlternatingGroup( [ 1 .. 4 ] ) -> AlternatingGroup( 
    [ 1 .. 4 ] ) >
    gap> m := TransformationNearRingByGenerators ( g, [t] );
    TransformationNearRingByGenerators(
    [ <mapping: AlternatingGroup( [ 1 .. 4 ] ) -> AlternatingGroup( 
        [ 1 .. 4 ] ) > ])
    gap> Size (m); # may take a few moments
    20736
    gap> IsCommutative ( m );
    false
\endexample

\>TransformationNearRingByAdditiveGenerators( <G>, <endomaplist> )

If a transformation nearring is known to be additively generated by a
set of endomappings on a group (as for example the distributively
generated nearrings $E(G)$, $A(G)$ and $I(G)$), the function
`Trans\-formation\-NearRing\-By\-Additive\-Generators' allows to
construct this nearring. The only difference between
`TransformationNearRingByGenerators' and
`Trans\-formation\-NearRing\-By\-Additive\-Generators' is that
`Trans\-formation\-NearRing\-By\-Additive\-Generators' is much faster.

\beginexample
    gap> G := SymmetricGroup(3);;
    gap> endos := Endomorphisms ( G );
    [ [ (1,2,3), (1,2) ] -> [ (), () ], [ (1,2,3), (1,2) ] -> [ (), (2,3) ], 
      [ (1,2,3), (1,2) ] -> [ (), (1,2) ], [ (1,2,3), (1,2) ] -> [ (), (1,3) ], 
      [ (1,2,3), (1,2) ] -> [ (1,2,3), (2,3) ], 
      [ (1,2,3), (1,2) ] -> [ (1,3,2), (2,3) ], 
      [ (1,2,3), (1,2) ] -> [ (1,3,2), (1,2) ], 
      [ (1,2,3), (1,2) ] -> [ (1,2,3), (1,2) ], 
      [ (1,2,3), (1,2) ] -> [ (1,2,3), (1,3) ], 
      [ (1,2,3), (1,2) ] -> [ (1,3,2), (1,3) ] ]
    gap> Endo := TransformationNearRingByAdditiveGenerators ( G, endos );
    < transformation nearring with 10 generators >
    gap> Size( Endo );
    54
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Nearrings of transformations}


\>MapNearRing( <G> )

\>TransformationNearRing( <G> )

`MapNearRing' and `TransformationNearRing' both return the nearring of all
mappings on <G>.

\beginexample
    gap> m := MapNearRing ( GTW32_12 );
    TransformationNearRing(32/12)
    gap> Size ( m );
    1461501637330902918203684832716283019655932542976
    gap> NearRingIdeals ( m );
    [ < nearring ideal >, < nearring ideal > ]
\endexample

\>IsFullTransformationNearRing( <tfmnr> )

The function `IsFullTransformationNearRing' returns `true' if the
transformation nearring <tfmnr> is the nearring of all mappings over
the group.

\beginexample
    gap> g := CyclicGroup ( 4 );
    <pc group of size 4 with 2 generators>
    gap> m := MapNearRing ( g );
    TransformationNearRing(<pc group of size 4 with 2 generators>)
    gap> gens := Filtered ( AsList ( m ), 
    >       f -> IsFullTransformationNearRing ( 
    >               TransformationNearRingByGenerators ( g, [ f ] )));;
    gap> Length(gens);
    12
\endexample

\>PolynomialNearRing( <G> )

`PolynomialNearRing' returns the nearring of all polynomial functions on <G>.

\beginexample
    gap> P := PolynomialNearRing ( GTW16_6 );
    PolynomialNearRing( 16/6 )
    gap> Size ( P );
    256
\endexample
    
\>EndomorphismNearRing( <G> )

`EndomorphismNearRing' returns the nearring generated by all endomorphisms
on <G>.

\beginexample
    gap> ES4 := EndomorphismNearRing ( SymmetricGroup ( 4 ) );
    EndomorphismNearRing( Sym( [ 1 .. 4 ] ) )
    gap> Size ( ES4 );
    927712935936
\endexample

\>AutomorphismNearRing( <G> )

`AutomorphismNearRing' returns the nearring generated by all automorphisms
on <G>.

\beginexample
    gap> A := AutomorphismNearRing ( DihedralGroup ( 8 ) );
    AutomorphismNearRing( <pc group of size 8 with 3 generators> )
    gap> Length(NearRingRightIdeals ( A ));
    28
    gap> Size (A);
    32
\endexample

\>InnerAutomorphismNearRing( <G> )

`InnerAutomorphismNearRing' returns the nearring generated by all inner
automorphisms on <G>.

\beginexample
    gap> I := InnerAutomorphismNearRing ( AlternatingGroup ( 4 ) );
    InnerAutomorphismNearRing( Alt( [ 1 .. 4 ] ) )
    gap> Size ( I );
    3072
    gap> m := Enumerator( I )[1000];
    <mapping: AlternatingGroup( [ 1 .. 4 ] ) -> AlternatingGroup( [ 1 .. 4 ] ) >
    gap> graph := List ( AsList ( AlternatingGroup ( 4 ) ),
    > x -> [x, Image (m, x)] );
    [ [ (), () ], [ (2,3,4), (1,4)(2,3) ], [ (2,4,3), (1,4)(2,3) ],
      [ (1,2)(3,4), (1,2)(3,4) ], [ (1,2,3), (1,3)(2,4) ],
      [ (1,2,4), (1,4)(2,3) ], [ (1,3,2), (1,4)(2,3) ], [ (1,3,4), (1,2)(3,4) ],
      [ (1,3)(2,4), (1,3)(2,4) ], [ (1,4,2), () ], [ (1,4,3), (1,4)(2,3) ],
      [ (1,4)(2,3), (1,4)(2,3) ] ]
\endexample

\>CompatibleFunctionNearRing( <G> )

`CompatibleFunctionNearRing' returns the nearring of all compatible functions
on the group <G>. A function $m:G \rightarrow G$ is compatible iff for every normal
subgroup $N$ of $G$ and all $g,h \in G$ if $g$ and $h$ are in the same coset of $N$
then their images under $m$ are in the same coset of $G$.

\>ZeroSymmetricCompatibleFunctionNearRing( <G> )

`ZeroSymmetricCompatibleFunctionNearRing' returns the nearring of all zerosymmetric
compatible functions on the group <G>. This function is also called by 
`CompatibleFunctionNearRing'.

\>IsCompatibleEndoMapping( <m> )

`IsCompatibleEndoMapping' returns `true' iff <m> is a compatible function on its 
source.

\>Is1AffineComplete( <G> )

A group <G> is called 1-affine complete, iff every compatible function on <G> is
polynomial. `Is1AffineComplete' returns `true' iff <G> is 1-affine complete.

\>CentralizerNearRing( <G>, <endos> )

`CentralizerNearRing' returns the nearring of all functions
$m:G \rightarrow G$ such that for all endomorphisms $e$ in <endos> the
equality $m \circ e = e \circ m$ holds.

\beginexample
    gap> autos := Automorphisms ( GTW8_4 );
    [ IdentityMapping( 8/4 ), ^(2,4),
      [ (1,2,3,4), (2,4) ] -> [ (1,4,3,2), (1,2)(3,4) ],
      [ (1,2,3,4), (2,4) ] -> [ (1,2,3,4), (1,2)(3,4) ], ^(1,4)(2,3),
      ^(1,2,3,4), [ (1,2,3,4), (2,4) ] -> [ (1,2,3,4), (1,4)(2,3) ],
      [ (1,4)(2,3), (1,4,3,2) ] -> [ (2,4), (1,2,3,4) ] ]
    gap> C := CentralizerNearRing ( GTW8_4, autos );
    CentralizerNearRing( 8/4, ... )
    gap> C0 := ZeroSymmetricPart ( C );
    < transformation nearring with 4 generators >
    gap> Size ( C0 );
    32
    gap> Is := NearRingIdeals ( C0 );
    [ < nearring ideal >, < nearring ideal >, < nearring ideal >,
      < nearring ideal >, < nearring ideal >, < nearring ideal >,
      < nearring ideal >, < nearring ideal >, < nearring ideal >,
      < nearring ideal >, < nearring ideal >, < nearring ideal >,
      < nearring ideal > ]
    gap> List (Is, Size);
    [ 1, 2, 4, 2, 4, 8, 8, 16, 4, 8, 16, 16, 32 ]
\endexample

\>RestrictedEndomorphismNearRing( <G>, <U> )

`RestrictedEndomorphismNearRing' returns the nearring generated by all
endomorphisms $e$ on $G$ with $e(G) \subseteq U$.

\beginexample
    gap> G := GTW16_8;
    16/8
    gap> U := First ( NormalSubgroups ( G ),
    >              x -> Size (x) = 2 );
    Group([ ( 1, 5)( 2,10)( 3,11)( 4,12)( 6,15)( 7,16)( 8, 9)(13,14) ])
    gap> HGU := RestrictedEndomorphismNearRing (G, U);
    RestrictedEndomorphismNearRing( 16/8, Group(
    [ ( 1, 5)( 2,10)( 3,11)( 4,12)( 6,15)( 7,16)( 8, 9)(13,14) ]) )
    gap> Size (HGU);
    8
    gap> IsDistributiveNearRing ( HGU );
    true
    gap> Filtered ( AsList ( HGU),
    >       x -> x = x * x );
    [ <mapping: 16/8 -> 16/8 > ]
\endexample
 
\>LocalInterpolationNearRing( <tfmnr>, <m> )

`LocalInterpolationNearRing' returns the nearring of all mappings on
$G$ that can be interpolated at any set of $m$ places by a mapping in
<tfmnr>, where $G$ is the domain and codomain of the elements in
<tfmnr>.

\beginexample
    gap> P := PolynomialNearRing ( GTW8_5 );
    PolynomialNearRing( 8/5 )
    gap> L := LocalInterpolationNearRing ( P, 2 );
    LocalInterpolationNearRing( PolynomialNearRing( 8/5 ), 2 )
    gap> Size ( L ) / Size ( P );
    16
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The group a transformation nearring acts on}

   
\>Gamma( <tfmnr> )

The function `Gamma' returns the group on which the mappings of the
nearring <tfmnr> act.

\beginexample
    gap> Gamma ( PolynomialNearRing ( CyclicGroup ( 25 ) ) );
    <pc group of size 25 with 2 generators>
    gap> IsCyclic (last);
    true
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Transformation nearrings and other nearrings}


\>AsTransformationNearRing( <nr> )

Provided that <nr> is not already a transformation nearring,
`AsTransformationNearRing' returns a transformation nearring that is isomorphic
to the nearring <nr>.

\beginexample
    gap> L := LibraryNearRing (GTW8_3, 12);
    LibraryNearRing(8/3, 12)
    gap> Lt := AsTransformationNearRing ( L );
    < transformation nearring with 3 generators >
    gap> Gamma ( Lt );
    8/3 x C_2
\endexample

\>AsExplicitMultiplicationNearRing( <nr> )

Provided that <nr> is not already an explicit multiplication nearring
(i. e. a transformation nearring), `AsExplicitMultiplicationNearRing' returns
an explicit multiplication nearring that is isomorphic to the nearring <nr>.

\beginexample
    gap> P := PolynomialNearRing ( GTW4_2 );
    PolynomialNearRing( 4/2 )
    gap> n := AsExplicitMultiplicationNearRing ( P );
    ExplicitMultiplicationNearRing ( Group(
    [ ( 1, 2)( 5, 6)( 9,10)(13,14), ( 3, 4)( 7, 8)(11,12)(15,16), 
      ( 7, 8)( 9,10)(13,14)(15,16) ]) , multiplication )
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Noetherian quotients for transformation nearrings}


\>NoetherianQuotient( <tfmnr>, <target>, <source> )!{for transformation nearrings}

`NoetherianQuotient' returns the set of all mappings $t$ in <tfmnr>
with $t(`source') \subseteq `target'$.

\beginexample
    gap> G := SymmetricGroup ( 4 );
    Sym( [ 1 .. 4 ] )
    gap> V := First ( NormalSubgroups ( G ), x -> Size ( x ) = 4 );
    Group([ (1,4)(2,3), (1,3)(2,4) ])
    gap> P := InnerAutomorphismNearRing ( G );
    InnerAutomorphismNearRing( Sym( [ 1 .. 4 ] ) )
    gap> N := NoetherianQuotient ( P, V, G );
    NoetherianQuotient( Group([ (1,4)(2,3), (1,3)(2,4) ]) ,Sym(
    [ 1 .. 4 ] ) )
    gap> Size ( P ) / Size ( N );
    54
\endexample

\>CongruenceNoetherianQuotient( <P>, <A>, <B>, <C> )!{for nearrings of polynomial functions}

`CongruenceNoetherianQuotient' returns the ideal of all those  mappings in <P> that
map every element of the group Gamma(P) into <C>, and maps two elements that
are congruent modulo <B> into elements that are congruent modulo <A>.
Input conditions: (1) <P> is the nearring of polynomial functions on a group G,
                  (2) <A> is a normal subgroup of G,
                  (3) <B> is a normal subgroup of G,
                  (4) <C> is a normal subgroup of G,
                  (5) [C,B] is less or equal to A.
\beginexample
    gap> G := GTW8_4;
    8/4
    gap> P := PolynomialNearRing (G);
    PolynomialNearRing( 8/4 )
    gap> A := TrivialSubgroup (G);
    Group(())
    gap> B := DerivedSubgroup (G);
    Group([ (1,3)(2,4) ])
    gap> C := G;
    8/4
    gap> I := CongruenceNoetherianQuotient (P, A, B, C);
    < nearring ideal >
    gap> Size (P/I);
    2
\endexample

\>CongruenceNoetherianQuotientForInnerAutomorphismNearRings (<I>, <A>, <B>, <C> )!{for inner automorphism nearrings}

`CongruenceNoetherianQuotientForInnerAutomorphismNearRings' returns the ideal of all those  mappings in <I> that
map every element of the group Gamma(I) into <C>, and maps two elements that
are congruent modulo <B> into elements that are congruent modulo <A>.
Input conditions: (1) <P> is the nearring of polynomial functions on a group G,
                  (2) <A> is a normal subgroup of G,
                  (3) <B> is a normal subgroup of G,
                  (4) <C> is a normal subgroup of G,
                  (5) [C,B] is less or equal to A.
\beginexample
    gap> G := GTW8_4;
    8/4
    gap> I := InnerAutomorphismNearRing (G);
    InnerAutomorphismNearRing( 8/4 )
    gap> A := TrivialSubgroup (G);
    Group(())
    gap> B := DerivedSubgroup (G);
    Group([ (1,3)(2,4) ])
    gap> C := G;
    8/4
    gap> j := CongruenceNoetherianQuotientForInnerAutomorphismNearRings (I,A,B,C);
    < nearring ideal >
    gap> Size (I/j);
    2
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Zerosymmetric mappings}


\>ZeroSymmetricPart( <tfmnr> )!{for transformation nearrings}

`ZeroSymmetricPart' returns the nearring of all mappings $t$ in
        <tfmnr> with $t(0) = 0$.

\beginexample
    gap> g := GTW8_4;
    8/4
    gap> P := PolynomialNearRing ( g );
    PolynomialNearRing( 8/4 )
    gap> Zp := ZeroSymmetricPart ( P );
    < transformation nearring with 4 generators >
    gap> InnerAutomorphismNearRing ( g ) = Zp;
    true
\endexample


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: