Quelle CHAP005.htm Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/sonata/doc/htm/ref/CHAP005.htm

<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>

<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>

In the previous chapter we introduced mappings on groups, and we
called them endomappings. 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 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 <a href="biblio.htm#Pilz:Nearrings"><[>Pilz:Nearrings</cite></a>], <a href="biblio.htm#meldrum85:NATLWG"><[>meldrum85:NATLWG</cite></a>],
and <a href="biblio.htm#Clay:Nearrings"><[>Clay:Nearrings</cite></a>],

The algorithms used can be found in
<a href="biblio.htm#aichingereckernoebauer00:TUOCINT"><[>aichingereckernoebauer00:TUOCINT</cite></a>] and <a href="biblio.htm#aichingerea00:CWN"><[>aichingerea00:CWN</cite></a>].

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'').


<h2><a name="SECT001">5.1 Constructing transformation nearrings</a></h2>

<a name = "SSEC001.1"></a>
<li><code>TransformationNearRingByGenerators( </code><var>G</var><code>, </code><var>endomaplist</var><code> )</code>

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>.

<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>

<a name = "SSEC001.2"></a>
<li><code>TransformationNearRingByAdditiveGenerators( </code><var>G</var><code>, </code><var>endomaplist</var><code> )</code>

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
<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.

<pre>
 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
</pre>


<h2><a name="SECT002">5.2 Nearrings of transformations</a></h2>

<a name = "SSEC002.1"></a>
<li><code>MapNearRing( </code><var>G</var><code> )</code>

<a name = "SSEC002.2"></a>
<li><code>TransformationNearRing( </code><var>G</var><code> )</code>

<code>MapNearRing</code> and <code>TransformationNearRing</code> both return the nearring of all
mappings on <var>G</var>.

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

<a name = "SSEC002.3"></a>
<li><code>IsFullTransformationNearRing( </code><var>tfmnr</var><code> )</code>

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.

<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>

<a name = "SSEC002.4"></a>
<li><code>PolynomialNearRing( </code><var>G</var><code> )</code>

<code>PolynomialNearRing</code> returns the nearring of all polynomial functions on <var>G</var>.

<pre>
 gap> P := PolynomialNearRing ( GTW16_6 );
 PolynomialNearRing( 16/6 )
 gap> Size ( P );
 256
</pre>

<a name = "SSEC002.5"></a>
<li><code>EndomorphismNearRing( </code><var>G</var><code> )</code>

<code>EndomorphismNearRing</code> returns the nearring generated by all endomorphisms
on <var>G</var>.

<pre>
 gap> ES4 := EndomorphismNearRing ( SymmetricGroup ( 4 ) );
 EndomorphismNearRing( Sym( [ 1 .. 4 ] ) )
 gap> Size ( ES4 );
 927712935936
</pre>

<a name = "SSEC002.6"></a>
<li><code>AutomorphismNearRing( </code><var>G</var><code> )</code>

<code>AutomorphismNearRing</code> returns the nearring generated by all automorphisms
on <var>G</var>.

<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>

<a name = "SSEC002.7"></a>
<li><code>InnerAutomorphismNearRing( </code><var>G</var><code> )</code>

<code>InnerAutomorphismNearRing</code> returns the nearring generated by all inner
automorphisms on <var>G</var>.

<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>

<a name = "SSEC002.8"></a>
<li><code>CompatibleFunctionNearRing( </code><var>G</var><code> )</code>

<code>CompatibleFunctionNearRing</code> returns the nearring of all compatible functions
on the group <var>G</var>. A function m:G → G is compatible iff for every normal
subgroup N of G and all g,h ∈ G if g and h are in the same coset of N
then their images under m are in the same coset of G.

<a name = "SSEC002.9"></a>
<li><code>ZeroSymmetricCompatibleFunctionNearRing( </code><var>G</var><code> )</code>

<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>.

<a name = "SSEC002.10"></a>
<li><code>IsCompatibleEndoMapping( </code><var>m</var><code> )</code>

<code>IsCompatibleEndoMapping</code> returns <code>true</code> iff <var>m</var> is a compatible function on its
source.

<a name = "SSEC002.11"></a>
<li><code>Is1AffineComplete( </code><var>G</var><code> )</code>

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.

<a name = "SSEC002.12"></a>
<li><code>CentralizerNearRing( </code><var>G</var><code>, </code><var>endos</var><code> )</code>

<code>CentralizerNearRing</code> returns the nearring of all functions
m:G → G such that for all endomorphisms e in <var>endos</var> the
equality m °e = e °m holds.

<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>

<a name = "SSEC002.13"></a>
<li><code>RestrictedEndomorphismNearRing( </code><var>G</var><code>, </code><var>U</var><code> )</code>

<code>RestrictedEndomorphismNearRing</code> returns the nearring generated by all
endomorphisms e on G with e(G) ⊆ U.

<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>

<a name = "SSEC002.14"></a>
<li><code>LocalInterpolationNearRing( </code><var>tfmnr</var><code>, </code><var>m</var><code> )</code>

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

<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>


<h2><a name="SECT003">5.3 The group a transformation nearring acts on</a></h2>

<a name = "SSEC003.1"></a>
<li><code>Gamma( </code><var>tfmnr</var><code> )</code>

The function <code>Gamma</code> returns the group on which the mappings of the
nearring <var>tfmnr</var> act.

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


<h2><a name="SECT004">5.4 Transformation nearrings and other nearrings</a></h2>

<a name = "SSEC004.1"></a>
<li><code>AsTransformationNearRing( </code><var>nr</var><code> )</code>

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>.

<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>

<a name = "SSEC004.2"></a>
<li><code>AsExplicitMultiplicationNearRing( </code><var>nr</var><code> )</code>

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>.

<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>


<h2><a name="SECT005">5.5 Noetherian quotients for transformation nearrings</a></h2>

<a name = "SSEC005.1"></a>
<li><code>NoetherianQuotient( </code><var>tfmnr</var><code>, </code><var>target</var><code>, </code><var>source</var><code> )</code>

<code>NoetherianQuotient</code> returns the set of all mappings t in <var>tfmnr</var>
with t(<tt>source</tt>) ⊆ <tt>target</tt>.

<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>

<a name = "SSEC005.2"></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>

<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>

<a name = "SSEC005.3"></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>

<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>


<h2><a name="SECT006">5.6 Zerosymmetric mappings</a></h2>

<a name = "SSEC006.1"></a>
<li><code>ZeroSymmetricPart( </code><var>tfmnr</var><code> )</code>

<code>ZeroSymmetricPart</code> returns the nearring of all mappings t in
 <var>tfmnr</var> with t(0) = 0.

<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>


[<a href = "chapters.htm">Up</a>] [<a href ="CHAP004.htm">Previous</a>] [<a href ="CHAP006.htm">Next</a>] [<a href = "theindex.htm">Index</a>]

<address>SONATA manual September 2025
</address></body></html>

quality100%

¤ Dauer der Verarbeitung: 0.34 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.