chap3.txt

  
  3 Circle functions
  
  To use the Circle package first you need to load it as follows:
  
    Example  
    
    gap> LoadPackage("circle");
    -----------------------------------------------------------------------------
    Loading  Circle 1.4.0 (Adjoint groups of finite rings)
    by Alexander Konovalov (http://www.cs.st-andrews.ac.uk/~alexk/) and
       Panagiotis Soules ([email protected]).
    -----------------------------------------------------------------------------
    true
    gap>
    
  
  
  Note  that  if  you  entered examples from the previous chapter, you need to
  restart GAP before loading the Circle package.
  
  
  3.1 Circle objects
  
  Because  for  elements  of the ring R the ordinary multiplication is already
  denoted  by  *,  for  the implementation of the circle multiplication in the
  adjoint  semigroup  we  need  to wrap up ring elements as CircleObjects, for
  which * is defined to be the circle multiplication.
  
  3.1-1 CircleObject
  
  CircleObject( x )  attribute
  
  Let  x  be  a  ring  element. Then CircleObject(x) returns the corresponding
  circle object. If x lies in the family fam, then CircleObject(x) lies in the
  family CircleFamily (3.1-5), corresponding to the family fam.
  
    Example  
    
    gap> a := CircleObject( 2 );
    CircleObject( 2 )
    
  
  
  3.1-2 UnderlyingRingElement
  
  UnderlyingRingElement( x )  attribute
  
  Returns the corresponding ring element for the circle object x.
  
    Example  
    
    gap> a := CircleObject( 2 );
    CircleObject( 2 )
    gap> UnderlyingRingElement( a );    
    2
    
  
  
  3.1-3 IsCircleObject
  
  IsCircleObject( x )  Category
  IsCircleObjectCollection( x )  Category
  
  An  object x lies in the category IsCircleObject if and only if it lies in a
  family  constructed  by  CircleFamily  (3.1-5).  Since circle objects can be
  multiplied  via  * with elements in their family, and we need operations One
  and   Inverse  to  deal  with  groups  they  generate,  circle  objects  are
  implemented in the category IsMultiplicativeElementWithInverse. A collection
  of  circle objects (e.g. adjoint semigroup or adjoint group) will lie in the
  category IsCircleObjectCollection.
  
    Example  
    
    gap> IsCircleObject( 2 ); IsCircleObject( CircleObject( 2 ) );            
    false
    true
    gap> IsMultiplicativeElementWithInverse( CircleObject( 2 ) );
    true
    gap> IsCircleObjectCollection( [ CircleObject(0), CircleObject(2) ] );
    true
    
  
  
  3.1-4 IsPositionalObjectOneSlotRep
  
  IsPositionalObjectOneSlotRep( x )  Representation
  IsDefaultCircleObject( x )  Representation
  
  To  store  the  corresponding  circle  object,  we  need  only  to store the
  underlying  ring  element.  Since this is quite common situation, we defined
  the  representation  IsPositionalObjectOneSlotRep  for  a more general case.
  Then     we     defined    IsDefaultCircleObject    as    a    synonym    of
  IsPositionalObjectOneSlotRep for objects in IsCircleObject (3.1-3).
  
    Example  
    
    gap> IsPositionalObjectOneSlotRep( CircleObject( 2 ) );
    true
    gap> IsDefaultCircleObject( CircleObject( 2 ) );                          
    true
    
  
  
  3.1-5 CircleFamily
  
  CircleFamily( fam )  attribute
  
  CircleFamily(fam)   is  a  family,  elements  of  which  are  in  one-to-one
  correspondence  with  elements  of  the  family  fam,  but  with  the circle
  multiplication  as  an  infix  multiplication. That is, for x, y in fam, the
  product  of their images in the CircleFamily(fam) will be the image of x + y
  +  x y. The relation between these families is demonstrated by the following
  equality:
  
    Example  
    
    gap> FamilyObj( CircleObject ( 2 ) ) = CircleFamily( FamilyObj( 2 ) );
    true
    
  
  
  
  3.2 Operations with circle objects
  
  3.2-1 One
  
  One( x )  operation
  
  This  operation  returns  the  multiplicative neutral element for the circle
  object  x.  The  result  is  the circle object corresponding to the additive
  neutral element of the appropriate ring.
  
    Example  
    
    gap> One( CircleObject( 5 ) );
    CircleObject( 0 )
    gap> One( CircleObject( 5 ) ) = CircleObject( Zero( 5 ) );
    true
    gap> One( CircleObject( [ [ 1, 1 ],[ 0, 1 ] ] ) );
    CircleObject( [ [ 0, 0 ], [ 0, 0 ] ] )
    
  
  
  3.2-2 InverseOp
  
  InverseOp( x )  operation
  
  For  a circle object x, returns the multiplicative inverse of x with respect
  to  the  circle  multiplication;  if  such  one  does not exist then fail is
  returned.
  
  In our implementation we assume that the underlying ring is a subring of the
  ring  with one, thus, if the circle inverse for an element x exists, than it
  can be computed as -x(1+x)^-1.
  
    Example  
    
    gap> CircleObject( -2 )^-1;                        
    CircleObject( -2 )
    gap> CircleObject( 2 )^-1; 
    CircleObject( -2/3 )
    gap> CircleObject( -2 )*CircleObject( -2 )^-1;
    CircleObject( 0 )
    
  
  
    Example  
    
    gap> m := CircleObject( [ [ 1, 1 ], [ 0, 1 ] ] );   
    CircleObject( [ [ 1, 1 ], [ 0, 1 ] ] )
    gap> m^-1;    
    CircleObject( [ [ -1/2, -1/4 ], [ 0, -1/2 ] ] )
    gap> m * m^-1;
    CircleObject( [ [ 0, 0 ], [ 0, 0 ] ] )
    gap> CircleObject( [ [ 0, 1 ], [ 1, 0 ] ] )^-1; 
    fail
    
  
  
  3.2-3 IsUnit
  
  IsUnit( [R, ]x )  operation
  
  Let x be a circle object corresponding to an element of the ring R. Then the
  operation  IsUnit  returns true, if x is invertible in R with respect to the
  circle multiplication, and false otherwise.
  
    Example  
    
    gap> IsUnit( Integers, CircleObject( -2 ) );
    true
    gap> IsUnit( Integers, CircleObject( 2 ) ); 
    false
    gap> IsUnit( Rationals, CircleObject( 2 ) );        
    true
    gap> IsUnit( ZmodnZ(8), CircleObject( ZmodnZObj(2,8) ) );
    true
    gap> m := CircleObject( [ [ 1, 1 ],[ 0, 1 ] ] );;
    gap> IsUnit( FullMatrixAlgebra( Rationals, 2 ), m );
    true
    
  
  
  If  the  first argument is omitted, the result will be returned with respect
  to the default ring of the circle object x.
  
    Example  
    
    gap> IsUnit( CircleObject( -2 ) );
    true
    gap> IsUnit( CircleObject( 2 ) ); 
    false
    gap> IsUnit( CircleObject( ZmodnZObj(2,8) ) );
    true
    gap> IsUnit( CircleObject( [ [ 1, 1 ],[ 0, 1 ] ] ) );                                    
    false
    
  
  
  3.2-4 IsCircleUnit
  
  IsCircleUnit( [R, ]x )  operation
  
  Let  x  be  an  element  of the ring R. Then IsCircleUnit( R, x ) determines
  whether x is invertible in R with respect to the circle multilpication. This
  is  equivalent  to the condition that 1+x is a unit in R with respect to the
  ordinary multiplication.
  
    Example  
    
    gap> IsCircleUnit( Integers, -2 );
    true
    gap> IsCircleUnit( Integers, 2 ); 
    false
    gap> IsCircleUnit( Rationals, 2 );          
    true
    gap> IsCircleUnit( ZmodnZ(8), ZmodnZObj(2,8) ); 
    true
    gap> m := [ [ 1, 1 ],[ 0, 1 ] ];                
    [ [ 1, 1 ], [ 0, 1 ] ]
    gap> IsCircleUnit( FullMatrixAlgebra(Rationals,2), m );
    true
    
  
  
  If  the  first argument is omitted, the result will be returned with respect
  to the default ring of x.
  
    Example  
    
    gap> IsCircleUnit( -2 );                               
    true
    gap> IsCircleUnit( 2 ); 
    false
    gap> IsCircleUnit( ZmodnZObj(2,8) );           
    true
    gap> IsCircleUnit( [ [ 1, 1 ],[ 0, 1 ] ] ); 
    false
    
  
  
  
  3.3 Construction of the adjoint semigroup and adjoint group
  
  3.3-1 AdjointSemigroup
  
  AdjointSemigroup( R )  attribute
  
  If  R is a finite ring then AdjointSemigroup(R) will return the monoid which
  is formed by all elements of R with respect to the circle multiplication.
  
  The implementation is rather straightforward and was added to provide a link
  to  the GAP functionality for semigroups. It assumes that the enumaration of
  all elements of the ring R is feasible.
  
    Example  
    
    gap> R:=Ring( [ ZmodnZObj(2,8) ] );
    <ring with 1 generators>
    gap> S:=AdjointSemigroup(R);
    <monoid with 4 generators>
    
  
  
  3.3-2 AdjointGroup
  
  AdjointGroup( R )  attribute
  
  If  R  is  a  finite  radical  algebra  then AdjointGroup(R) will return the
  adjoint group of R, given as a group generated by a set of circle objects.
  
  To  compute  the  adjoint group of a finite radical algebra, Circle uses the
  fact that all elements of a radical algebra form a group with respect to the
  circle  multiplication.  Thus,  the  adjoint  group  of  R  coincides with R
  elementwise, and we can randomly select an appropriate set of generators for
  the adjoint group.
  
  The  warning  is displayed by IsGeneratorsOfMagmaWithInverses method defined
  in gap4r4/lib/grp.gi and may be ignored.
  
  WARNINGS:
  
  1.  The  set  of  generators  of  the returned group is not required to be a
  generating set of minimal possible order.
  
  2.  AdjointGroup  is  stored as an attribute of R, so for the same copy of R
  calling  it  again  you  will  get  the  same result. But if you will create
  another copy of R in the future, the output may differ because of the random
  selection  of  generators. If you want to have the same generating set, next
  time you should construct a group immediately specifying circle objects that
  generate it.
  
  3. In most cases, to investigate some properties of the adjoint group, it is
  necessary  first  to  convert  it to an isomorphic permutation group or to a
  PcGroup.
  
  For  example,  we can create the following commutative 2-dimensional radical
  algebra of order 4 over the field of two elements, and show that its adjoint
  group is a cyclic group of order 4:
  
    Example  
    
    gap> x:=[ [ 0, 1, 0 ],
    >         [ 0, 0, 1 ],
    >         [ 0, 0, 0 ] ];;
    gap> R := Algebra( GF(2), [ One(GF(2))*x ] );  
    <algebra over GF(2), with 1 generators>
    gap> RadicalOfAlgebra( R ) = R;
    true
    gap> Dimension(R);
    2
    gap> G := AdjointGroup( R );;
    gap> Size( R ) = Size( G );
    true
    gap> StructureDescription( G );
    "C4"
    
  
  
  In  the  following  example  we  construct  a  non-commutative 3-dimensional
  radical  algebra  of order 8 over the field of two elements, and demonstrate
  that its adjoint group is the dihedral group of order 8:
  
    Example  
    
    gap> x:=[ [ 0, 1, 0 ],
    >         [ 0, 0, 0 ],     
    >         [ 0, 0, 0 ] ];;
    gap> y:=[ [ 0, 0, 0 ],     
    >         [ 0, 0, 1 ],  
    >         [ 0, 0, 0 ] ];;
    gap> R := Algebra( GF(2), One(GF(2))*[x,y] );  
    <algebra over GF(2), with 2 generators>
    gap> RadicalOfAlgebra(R) = R;                
    true
    gap> Dimension(R);
    3
    gap> G := AdjointGroup( R );
    <group of size 8 with 2 generators>
    gap> StructureDescription( G );
    "D8"
    
  
  
  If  the  ring  R  is  not  a  radical  algebra, then Circle will use another
  approach. We will enumerate all elements of the ring R and select those that
  are  units  with  respect  to  the circle multiplication. Then we will use a
  random  approach  similar  to  the case of the radical algebra, to find some
  generating  set  of  the  adjoint group. Again, all warnings 1-3 above refer
  also to this case.
  
  Of  course,  enumeration  of  all  elements of R should be feasible for this
  computation. In the following example we demonstrate how it works for rings,
  generated by residue classes:
  
    Example  
    
    gap> R := Ring( [ ZmodnZObj(2,8) ] );
    <ring with 1 generators>
    gap> G := AdjointGroup( R );
    <group of size 4 with 2 generators>
    gap> StructureDescription( G );
    "C2 x C2"
    gap> R := Ring( [ ZmodnZObj(2,256) ] );   
    <ring with 1 generators>
    gap> G := AdjointGroup( R );;
    gap> StructureDescription( G );
    "C64 x C2"
    
  
  
  Due  to  the  AdjointSemigroup (3.3-1), there is also another way to compute
  the  adjoint  group  of  a ring R by means of the computation of its adjoint
  semigroup  S(R) and taking the Green's H-class of the multiplicative neutral
  element of S(R). Let us repeat the last example in this way:
  
    Example  
    
    gap> R := Ring( [ ZmodnZObj(2,256) ] );  
    <ring with 1 generators>
    gap> S := AdjointSemigroup( R );
    <monoid with 128 generators>
    gap> H := GreensHClassOfElement(S,One(S));
    <Green's H-class: <object>>
    gap> G:=AsGroup(H);
    <group of size 128 with 2 generators>
    gap> StructureDescription(G);
    "C64 x C2"
    
  
  
  However,  the  conversion  of the Green's H-class to the group may take some
  time which may vary dependently on the particular ring in question, and will
  also     display     a     lot     of    warnings    about    the    default
  IsGeneratorsOfMagmaWithInverses method, so we did not implemented this as as
  standard  method.  In  the  following  example  the  method based on Green's
  H-class  is  much  slower  than  an  application of earlier described random
  approach (20s vs 10ms):
  
    Example  
    
    gap> R := Ring( [ ZmodnZObj(2,256) ] );   
    <ring with 1 generators>
    gap> AdjointGroup(R);;
    gap> R := Ring( [ ZmodnZObj(2,256) ] );
    <ring with 1 generators>
    gap> S:=AdjointSemigroup(R); 
    <monoid with 128 generators>
    gap> AsGroup(GreensHClassOfElement(S,One(S))); 
    <group of size 128 with 2 generators>
    
  
  
  Finally,  note  that  if R has a unity 1, then the set 1+R^ad, where R^ad is
  the  adjoint  semigroup  of  R,  coincides with the multiplicative semigroup
  R^mult  of  R,  and the map r ↦ (1+r) for r in R is an isomorphism from R^ad
  onto R^mult.
  
  Similarly,  the  set  1+R^*,  where R^* is the adjoint group of R, coincides
  with  the unit group of R, which we denote U(R), and the map r ↦ (1+r) for r
  in R is an isomorphism from R^* onto U(R).
  
  We demonstrate this isomorphism using the following example.
  
    Example  
    
    gap> LoadPackage( "laguna", false );
    true
    gap> FG := GroupRing( GF(2), DihedralGroup(8) );
    <algebra-with-one over GF(2), with 3 generators>
    gap> R := AugmentationIdeal( FG );;
    gap> G := AdjointGroup( R );;
    gap> IdGroup( G );
    [ 128, 170 ]
    gap> IdGroup( Units( FG ) );
    #I  LAGUNA package: Computing the unit group ...
    [ 128, 170 ]
    
  
  
  Thus,  dependently  on the ring R in question, it might be possible that you
  can compute much faster its unit group using Units(R) than its adjoint group
  using  AdjointGroup(R).  This  is  why  in  an attempt of computation of the
  adjoint group of the ring with one a warning message will be displayed:
  
    Example  
    
    gap> Size( AdjointGroup( GroupRing( GF(2), DihedralGroup(8) ) ) );
    
    WARNING: usage of AdjointGroup for associative ring <R> with one!!! 
    In this case the adjoint group is isomorphic to the unit group 
    Units(<R>), which possibly may be computed faster!!! 
    
    128
    gap> Size( AdjointGroup( Integers mod 11 ) );                  
    
    WARNING: usage of AdjointGroup for associative ring <R> with one!!! 
    In this case the adjoint group is isomorphic to the unit group 
    Units(<R>), which possibly may be computed faster!!! 
    
    10
    
  
  
  If R is infinite, an error message will appear, telling that Circle does not
  provide methods to deal with infinite rings.
  
  
  3.4 Service functions
  
  3.4-1 InfoCircle
  
  InfoCircle info class
  
  InfoCircle is a special Info class for Circle algorithms. It has 2 levels: 0
  (default)    and   1.   To   change   info   level   to   k,   use   command
  SetInfoLevel(InfoCircle, k).
  
    Example  
    
    gap> SetInfoLevel( InfoCircle, 1 );
    gap> SetInfoLevel(InfoCircle,1);
    gap> R := Ring( [ ZmodnZObj(2,8) ]);
    <ring with 1 generators>
    gap> G := AdjointGroup( R );
    #I  Circle : <R> is not a radical algebra, computing circle units ...
    #I  Circle : searching generators for adjoint group ...
    <group of size 4 with 2 generators>
    gap> SetInfoLevel( InfoCircle, 0 );