<html><head><title>[SONATA] 5 Transformation nearrings</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP004.htm">Previous</a>] [<a href ="CHAP006.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>5 Transformation nearrings</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP005.htm#SECT001">Constructing transformation nearrings</a>
<li> <A HREF="CHAP005.htm#SECT002">Nearrings of transformations</a>
<li> <A HREF="CHAP005.htm#SECT003">The group a transformation nearring acts on</a>
<li> <A HREF="CHAP005.htm#SECT004">Transformation nearrings and other nearrings</a>
<li> <A HREF="CHAP005.htm#SECT005">Noetherian quotients for transformation nearrings</a>
<li> <A HREF="CHAP005.htm#SECT006">Zerosymmetric mappings</a>
</ol><p>
<p>
In the previous chapter we introduced mappings on groups, and we
called them <strong>endomappings</strong>. We also introduced the operation of
pointwise addition <code>+</code> for endomappings. Now we are able to use these
mappings together with pointwise addition <code>+</code> and composition <code>*</code> to
construct left nearrings. These nearrings satisfy the distributive
law <var>x * (y + z) = x * y + x * z</var>.
<p>
A <strong>transformation nearring</strong> is a set of mappings on a group <var>G</var> that
is closed under pointwise addition of mappings, under forming the
additive inverse and under functional composition. For more
information we suggest citePilz:Nearrings, citemeldrum85:NATLWG,
and citeClay:Nearrings,
<p>
The algorithms used can be found in
citeaichingereckernoebauer00:TUOCINT and citeaichingerea00:CWN.
<p>
The elements of a transformation nearring are given as endomappings on
the group <var>G</var> (cf. Chapter ``Functions on groups that are not
necessarily homomorphisms: EndoMappings'').
<p>
<p>
<h2><a name="SECT001">5.1 Constructing transformation nearrings</a></h2>
<p><p>
<a name = "SECT001"></a>
<li><code>TransformationNearRingByGenerators( </code><var>G</var><code>, </code><var>endomaplist</var><code> )</code>
<p>
For a (possibly empty) list <var>endomaplist</var> of endomappings on a group
<var>G</var>, the constructor function <code>TransformationNearRingByGenerators</code> returns the
nearring generated by these mappings. All of them must be
endomappings on the group <var>G</var>.
<p>
<pre>
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
</pre>
<p>
<a name = "SECT001"></a>
<li><code>TransformationNearRingByAdditiveGenerators( </code><var>G</var><code>, </code><var>endomaplist</var><code> )</code>
<p>
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 <var>E(G)</var>, <var>A(G)</var> and <var>I(G)</var>), the function
<code>TransformationNearRingByAdditiveGenerators</code> allows to
construct this nearring. The only difference between
<code>TransformationNearRingByGenerators</code> and
<code>TransformationNearRingByAdditiveGenerators</code> is that
<code>TransformationNearRingByAdditiveGenerators</code> is much faster.
<p>
<pre>
gap> endos := Endomorphisms ( GTW6_2 );
[ [ (1,2), (1,2,3) ] -> [ (), () ], [ (1,2), (1,2,3) ] -> [ (2,3), () ],
[ (1,2), (1,2,3) ] -> [ (1,3), () ], [ (1,2), (1,2,3) ] -> [ (1,2), () ],
[ (1,2), (1,2,3) ] -> [ (2,3), (1,2,3) ],
[ (1,2), (1,2,3) ] -> [ (2,3), (1,3,2) ],
[ (1,2), (1,2,3) ] -> [ (1,2), (1,3,2) ],
[ (1,2), (1,2,3) ] -> [ (1,2), (1,2,3) ],
[ (1,2), (1,2,3) ] -> [ (1,3), (1,2,3) ],
[ (1,2), (1,2,3) ] -> [ (1,3), (1,3,2) ] ]
gap> Endo := TransformationNearRingByAdditiveGenerators ( GTW6_2, endos );
< transformation nearring with 10 generators >
gap> Size ( Endo );
54
</pre>
<p>
<p>
<h2><a name="SECT002">5.2 Nearrings of transformations</a></h2>
<p><p>
<a name = "SECT002"></a>
<li><code>MapNearRing( </code><var>G</var><code> )</code>
<p>
<a name = "SECT002"></a>
<li><code>TransformationNearRing( </code><var>G</var><code> )</code>
<p>
<code>MapNearRing</code> and <code>TransformationNearRing</code> both return the nearring of all
mappings on <var>G</var>.
<p>
<pre>
gap> m := MapNearRing ( GTW32_12 );
TransformationNearRing(32/12)
gap> Size ( m );
1461501637330902918203684832716283019655932542976
gap> NearRingIdeals ( m );
[ < nearring ideal >, < nearring ideal > ]
</pre>
<p>
<a name = "SECT002"></a>
<li><code>IsFullTransformationNearRing( </code><var>tfmnr</var><code> )</code>
<p>
The function <code>IsFullTransformationNearRing</code> returns <code>true</code> if the
transformation nearring <var>tfmnr</var> is the nearring of all mappings over
the group.
<p>
<pre>
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
</pre>
<p>
<a name = "SECT002"></a>
<li><code>PolynomialNearRing( </code><var>G</var><code> )</code>
<p>
<code>PolynomialNearRing</code> returns the nearring of all polynomial functions on <var>G</var>.
<p>
<pre>
gap> P := PolynomialNearRing ( GTW16_6 );
PolynomialNearRing( 16/6 )
gap> Size ( P );
256
</pre>
<p>
<a name = "SECT002"></a>
<li><code>EndomorphismNearRing( </code><var>G</var><code> )</code>
<p>
<code>EndomorphismNearRing</code> returns the nearring generated by all endomorphisms
on <var>G</var>.
<p>
<pre>
gap> ES4 := EndomorphismNearRing ( SymmetricGroup ( 4 ) );
EndomorphismNearRing( Sym( [ 1 .. 4 ] ) )
gap> Size ( ES4 );
927712935936
</pre>
<p>
<a name = "SECT002"></a>
<li><code>AutomorphismNearRing( </code><var>G</var><code> )</code>
<p>
<code>AutomorphismNearRing</code> returns the nearring generated by all automorphisms
on <var>G</var>.
<p>
<pre>
gap> A := AutomorphismNearRing ( DihedralGroup ( 8 ) );
AutomorphismNearRing( <pc group of size 8 with 3 generators> )
gap> Length(NearRingRightIdeals ( A ));
28
gap> Size (A);
32
</pre>
<p>
<a name = "SECT002"></a>
<li><code>InnerAutomorphismNearRing( </code><var>G</var><code> )</code>
<p>
<code>InnerAutomorphismNearRing</code> returns the nearring generated by all inner
automorphisms on <var>G</var>.
<p>
<pre>
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) ] ]
</pre>
<p>
<a name = "SECT002"></a>
<li><code>CompatibleFunctionNearRing( </code><var>G</var><code> )</code>
<p>
<code>CompatibleFunctionNearRing</code> returns the nearring of all compatible functions
on the group <var>G</var>. A function <var>m:G rightarrowG</var> is compatible iff for every normal
subgroup <var>N</var> of <var>G</var> and all <var>g,h inG</var> if <var>g</var> and <var>h</var> are in the same coset of <var>N</var>
then their images under <var>m</var> are in the same coset of <var>G</var>.
<p>
<a name = "SECT002"></a>
<li><code>ZeroSymmetricCompatibleFunctionNearRing( </code><var>G</var><code> )</code>
<p>
<code>ZeroSymmetricCompatibleFunctionNearRing</code> returns the nearring of all zerosymmetric
compatible functions on the group <var>G</var>. This function is also called by
<code>CompatibleFunctionNearRing</code>.
<p>
<a name = "SECT002"></a>
<li><code>IsCompatibleEndoMapping( </code><var>m</var><code> )</code>
<p>
<code>IsCompatibleEndoMapping</code> returns <code>true</code> iff <var>m</var> is a compatible function on its
source.
<p>
<a name = "SECT002"></a>
<li><code>Is1AffineComplete( </code><var>G</var><code> )</code>
<p>
A group <var>G</var> is called 1-affine complete, iff every compatible function on <var>G</var> is
polynomial. <code>Is1AffineComplete</code> returns <code>true</code> iff <var>G</var> is 1-affine complete.
<p>
<a name = "SECT002"></a>
<li><code>CentralizerNearRing( </code><var>G</var><code>, </code><var>endos</var><code> )</code>
<p>
<code>CentralizerNearRing</code> returns the nearring of all functions
<var>m:G rightarrowG</var> such that for all endomorphisms <var>e</var> in <var>endos</var> the
equality <var>m circe = e circm</var> holds.
<p>
<pre>
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 ]
</pre>
<p>
<a name = "SECT002"></a>
<li><code>RestrictedEndomorphismNearRing( </code><var>G</var><code>, </code><var>U</var><code> )</code>
<p>
<code>RestrictedEndomorphismNearRing</code> returns the nearring generated by all
endomorphisms <var>e</var> on <var>G</var> with <var>e(G) subseteqU</var>.
<p>
<pre>
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 > ]
</pre>
<p>
<a name = "SECT002"></a>
<li><code>LocalInterpolationNearRing( </code><var>tfmnr</var><code>, </code><var>m</var><code> )</code>
<p>
<code>LocalInterpolationNearRing</code> returns the nearring of all mappings on
<var>G</var> that can be interpolated at any set of <var>m</var> places by a mapping in
<var>tfmnr</var>, where <var>G</var> is the domain and codomain of the elements in
<var>tfmnr</var>.
<p>
<pre>
gap> P := PolynomialNearRing ( GTW8_5 );
PolynomialNearRing( 8/5 )
gap> L := LocalInterpolationNearRing ( P, 2 );
LocalInterpolationNearRing( PolynomialNearRing( 8/5 ), 2 )
gap> Size ( L ) / Size ( P );
16
</pre>
<p>
<p>
<h2><a name="SECT003">5.3 The group a transformation nearring acts on</a></h2>
<p><p>
<a name = "SECT003"></a>
<li><code>Gamma( </code><var>tfmnr</var><code> )</code>
<p>
The function <code>Gamma</code> returns the group on which the mappings of the
nearring <var>tfmnr</var> act.
<p>
<pre>
gap> Gamma ( PolynomialNearRing ( CyclicGroup ( 25 ) ) );
<pc group of size 25 with 2 generators>
gap> IsCyclic (last);
true
</pre>
<p>
<p>
<h2><a name="SECT004">5.4 Transformation nearrings and other nearrings</a></h2>
<p><p>
<a name = "SECT004"></a>
<li><code>AsTransformationNearRing( </code><var>nr</var><code> )</code>
<p>
Provided that <var>nr</var> is not already a transformation nearring,
<code>AsTransformationNearRing</code> returns a transformation nearring that is isomorphic
to the nearring <var>nr</var>.
<p>
<pre>
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
</pre>
<p>
<a name = "SECT004"></a>
<li><code>AsExplicitMultiplicationNearRing( </code><var>nr</var><code> )</code>
<p>
Provided that <var>nr</var> is not already an explicit multiplication nearring
(i. e. a transformation nearring), <code>AsExplicitMultiplicationNearRing</code> returns
an explicit multiplication nearring that is isomorphic to the nearring <var>nr</var>.
<p>
<pre>
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 )
</pre>
<p>
<p>
<h2><a name="SECT005">5.5 Noetherian quotients for transformation nearrings</a></h2>
<p><p>
<a name = "SECT005"></a>
<li><code>NoetherianQuotient( </code><var>tfmnr</var><code>, </code><var>target</var><code>, </code><var>source</var><code> )</code>
<p>
<code>NoetherianQuotient</code> returns the set of all mappings <var>t</var> in <var>tfmnr</var>
with <var>t(<code>source</code>) subseteq<code>target</code></var>.
<p>
<pre>
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
</pre>
<p>
<a name = "SECT005"></a>
<li><code>CongruenceNoetherianQuotient( </code><var>P</var><code>, </code><var>A</var><code>, </code><var>B</var><code>, </code><var>C</var><code> )</code>
<p>
<code>CongruenceNoetherianQuotient</code> returns the ideal of all those mappings in <var>P</var> that
map every element of the group Gamma(P) into <var>C</var>, and maps two elements that
are congruent modulo <var>B</var> into elements that are congruent modulo <var>A</var>.
Input conditions: (1) <var>P</var> is the nearring of polynomial functions on a group G,
(2) <var>A</var> is a normal subgroup of G,
(3) <var>B</var> is a normal subgroup of G,
(4) <var>C</var> is a normal subgroup of G,
(5) [C,B] is less or equal to A.
<pre>
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
</pre>
<p>
<a name = "SECT005"></a>
<li><code>CongruenceNoetherianQuotientForInnerAutomorphismNearRings (</code><var>I</var><code>, </code><var>A</var><code>, </code><var>B</var><code>, </code><var>C</var><code> )</code>
<p>
<code>CongruenceNoetherianQuotientForInnerAutomorphismNearRings</code> returns the ideal of all those mappings in <var>I</var> that
map every element of the group Gamma(I) into <var>C</var>, and maps two elements that
are congruent modulo <var>B</var> into elements that are congruent modulo <var>A</var>.
Input conditions: (1) <var>P</var> is the nearring of polynomial functions on a group G,
(2) <var>A</var> is a normal subgroup of G,
(3) <var>B</var> is a normal subgroup of G,
(4) <var>C</var> is a normal subgroup of G,
(5) [C,B] is less or equal to A.
<pre>
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
</pre>
<p>
<p>
<h2><a name="SECT006">5.6 Zerosymmetric mappings</a></h2>
<p><p>
<a name = "SECT006"></a>
<li><code>ZeroSymmetricPart( </code><var>tfmnr</var><code> )</code>
<p>
<code>ZeroSymmetricPart</code> returns the nearring of all mappings <var>t</var> in
<var>tfmnr</var> with <var>t(0) = 0</var>.
<p>
<pre>
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
</pre>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP004.htm">Previous</a>] [<a href ="CHAP006.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>SONATA manual<br>November 2008
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
2780
