Quelle CHAP005.htm Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/sonata/doc/htm/tut/CHAP005.htm

<html><head><title>[SONATA-tutorial] 5 Some interesting 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 Some interesting nearrings</h1>

<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP005.htm#SECT001">Nearrings generated by endomorphisms on a group</a>
<li> <A HREF="CHAP005.htm#SECT002">More information than just the size</a>
<li> <A HREF="CHAP005.htm#SECT003">Centralizer nearrings</a>
<li> <A HREF="CHAP005.htm#SECT004">Finding affine complete groups</a>
</ol>

One motivation for creating SONATA was to study
particular near-rings associated with a given
group G: the inner automorphism nearring
I(G), the automorphism nearring A(G), and
the endomorphism nearring E(G).
The nearring I(G) is the smallest subnearring of the
nearring M(G) of all mappings from G into G that
contains all inner automorphisms; similarly A(G) and E(G)
are defined. <a href="biblio.htm#meldrum85:NATLWG"><[>meldrum85:NATLWG</cite></a>] contains
a lot of information on these near-rings.


<h2><a name="SECT001">5.1 Nearrings generated by endomorphisms on a group</a></h2>

Let us compute the nearring I(A4), which is the nearring of all
zero-symmetric polynomial functions on the group A4.
<pre>
 gap> I := InnerAutomorphismNearRing ( AlternatingGroup ( 4 ) );
 InnerAutomorphismNearRing( Alt( [ 1 .. 4 ] ) )
 gap> Size (I);
 3072
</pre>

For a polynomial function, we can ask for a polynomial that induces it.

<pre>
 gap> p := Random( I );
 <mapping: AlternatingGroup( [ 1 .. 4 ] ) -> AlternatingGroup( [ 1 .. 4 ] ) >
 gap> PrintAsTerm( p );
 - g1 + g2 - x - g2 + g1 + g2 + g1 - x + g2 - x + 2 * g1 -
 3 * x - g1 + x + g2 - x - g2 + g1 + x - g1 + x - g1 + x +
 g1 + x - g2 - x + g2 - g1 - x + g1 + x
 gap> GeneratorsOfGroup( AlternatingGroup( 4 ) );
 [ (1,2,3), (2,3,4) ]
</pre>

We get a polynomial (not necessarily the shortest possible polynomial) that induces
the polynomial function. The expressions <code>g1</code> and <code>g2</code> stand for the first and second
generator of the group respectively.

Now we compute the nearring that is additively generated by the automorphisms
of the dihedral group of order 8. This nearring is usually called
A (D8).
<pre>
 gap> A := AutomorphismNearRing ( DihedralGroup ( 8 ) );
 AutomorphismNearRing( <pc group of size 8 with 3 generators> )
 gap> Size (A);
 32
</pre>

Much attention has been devoted to the nearring E (S4), which
is the nearring additively generated by the endomorphisms on the
symmetric group on four letters.
<pre>
 gap> EndS4 := EndomorphismNearRing ( SymmetricGroup ( 4 ) );
 EndomorphismNearRing( Sym( [ 1 .. 4 ] ) )
 gap> Size ( EndS4 );
 927712935936
 gap> F1 := last;;
 gap> Collected ( Factors( F1 ));
 [ [ 2, 35 ], [ 3, 3 ] ]
</pre>
In the last example, we have computed the size
of E (S4) as 235 ·33.

We have also included some less popular examples of nearrings.
One of those is the nearring H (G, U). This is the nearring
that is generated by all endomorphisms on G whose range lies in
the subgroup U of G.
We do an example on the group 16/8 in the classification of
Thomas and Wood. It is a subdirectly irreducible group of order 16,
and the factor modulo the monolith is isomorphic to the elementary abelian group
of order 8.
<pre>
 gap> G := GTW16_8;
 16/8
 gap> U := First ( NormalSubgroups( G ), N -> Size(N) = 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
</pre>
It is interesting to compare this nearring to the nearring of
all functions e in the endomorphism nearring E (G) with the
property e (G) ⊆ U.
<pre>
 gap> EofG := EndomorphismNearRing ( G );
 EndomorphismNearRing( 16/8 )
 gap> EGU := NoetherianQuotient ( EofG, U, G );
 NoetherianQuotient( Group(
 [ ( 1, 5)( 2,10)( 3,11)( 4,12)( 6,15)( 7,16)( 8, 9)(13,14) ]) ,16/8 )
 gap> Size ( EGU );
 128
</pre>
If N is a transformation nearring on G, and U, V are subsets of G then
<code>NoetherianQuotient (N,U,V)</code> returns the collection of all mappings
f ∈ N such that f(V) ⊆ U.


<h2><a name="SECT002">5.2 More information than just the size</a></h2>

In this section, we use SONATA to produce some interesting information
about the nearring I(S3), which is the nearring of all zero-symmetric polynomial
functions on the group S3.

<pre>
 gap> G := SymmetricGroup ( 3 );
 Sym( [ 1 .. 3 ] )
 gap> I := InnerAutomorphismNearRing ( G );
 InnerAutomorphismNearRing( Sym( [ 1 .. 3 ] ) )
 gap> Size( I );
 54
</pre>

Now we would like to see how many of these 54 functions are idempotent.
First a complicated version.
<pre>
 gap> Filtered ( I,
 > t -> ForAll( G, g -> Image(t, g) = Image(t, Image(t, g)) ) );;
 gap> Length( last );
 18
</pre>
Now a simpler version.
<pre>
 gap> Filtered ( I, i -> i^2 = i );;
 gap> Length( last );
 18
</pre>


<h2><a name="SECT003">5.3 Centralizer nearrings</a></h2>

Let Φ be a subset of the endomorphisms of a group G.
Then we define MΦ (G) as the set of all
mappings m : G → G that satisfy m °φ = φ°m for all φ ∈ Φ.
This set is closed under addition and composition of
mappings, and hence a subnearring of M(G).
The set MΦ (G) is called the centralizer nearring
of G determined by Φ. It need not necessarily be
zero-symmetric.

In the following examples, we compute the centralizer nearring
MEnd (S3) (S3).
<pre>
 gap> G := SymmetricGroup( 3 );
 Sym( [ 1 .. 3 ] )
 gap> endos := Endomorphisms( G );
 [ [ (1,2,3), (1,2) ] -> [ (), () ], [ (1,2,3), (1,2) ] -> [ (), (1,3) ],
 [ (1,2,3), (1,2) ] -> [ (), (2,3) ], [ (1,2,3), (1,2) ] -> [ (), (1,2) ],
 [ (1,2,3), (1,2) ] -> [ (1,2,3), (1,3) ],
 [ (1,2,3), (1,2) ] -> [ (1,3,2), (1,2) ],
 [ (1,2,3), (1,2) ] -> [ (1,3,2), (1,3) ],
 [ (1,2,3), (1,2) ] -> [ (1,2,3), (2,3) ],
 [ (1,2,3), (1,2) ] -> [ (1,2,3), (1,2) ],
 [ (1,2,3), (1,2) ] -> [ (1,3,2), (2,3) ] ]
 gap> C := CentralizerNearRing( G, endos );
 CentralizerNearRing( Sym( [ 1 .. 3 ] ), ... )
 gap> Size ( C );
 6
</pre>

An ideal of a nearring (N,+,*) is a subset I such that
I is a normal subgroup of (N,+), and
for all i ∈ I, n,m ∈ N, we have
(m+i)*n − m*n ∈ I and n*i ∈ I. Ideals are in
one-to-one correspondence to the congruence relations
on (N,+,*).

Do you think that this nearring is simple? Alan Cannon does not think so,
and, in fact, SONATA tells us:
<pre>
 gap> I := NearRingIdeals( C );
 [ < nearring ideal >, < nearring ideal >, < nearring ideal >,
 < nearring ideal > ]
 gap> List( I, Size );
 [ 1, 2, 3, 6 ]
</pre>
So, we have ideals of size 1,2,3 and 6.


<h2><a name="SECT004">5.4 Finding affine complete groups</a></h2>

We shall now construct all compatible (= congruence preserving) functions
on the group 16/6 (Thomas-Wood-notation); this is the 6th group
of order 16 in <a href="biblio.htm#thomaswood80:GT"><[>thomaswood80:GT</cite></a>].
It is the direct
product of D8 and C2. Let G be this group. We first
construct the nearring P(G) of all polynomial functions.
Then we construct all those functions that can be interpolated
at every subset of G with at most two elements by a function in
P(G) by using the function <code>LocalInterpolationNearRing</code>:
these are the compatible functions on G (see <a href="biblio.htm#Pilz:Nearrings"><[>Pilz:Nearrings</cite></a>)].
<pre>
 gap> P := PolynomialNearRing( GTW16_6 );
 PolynomialNearRing( 16/6 )
 gap> Size( P );
 256
 gap> C := LocalInterpolationNearRing(P, 2);
 LocalInterpolationNearRing( PolynomialNearRing( 16/6 ), 2 )
 gap> Size (C);
 256
</pre>
Hence the group 16/6 is 1-affine complete. A much faster algorithm for
computing the nearring of compatible functions can be used.
<pre>
 gap> C := CompatibleFunctionNearRing( GTW16_6 );
 < transformation nearring with 7 generators >
 gap> Size(C);
 256;
</pre>
Finally, the fastest way to decide 1-affine completeness is to use the function
<code>Is1AffineComplete</code>.
<pre>
 gap> Is1AffineComplete( GTW16_6 );
 true
</pre>

When studying polynomial functions on direct products of groups, it is
important to know the smallest positive number l such
that the zero-function can be expressed by a term
a1 + e1·x + a2 + …+ en·x + an+1 with
∑ei = l.
This l has been called the length of the group
by S.D.Scott.

<pre>
 gap> ScottLength( SymmetricGroup( 3 ) );
 2
</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-tutorial manual September 2025
</address></body></html>

Messung V0.5

¤ Dauer der Verarbeitung: 0.13 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 und die Messung sind noch experimentell.