67.20 ConstructivelyRecogniseClassical

In this section, we describe functions developed by Celler and Leedham-Green (see [4] for details) to recognise constructively classical groups in their natural representation over finite fields.

ConstructivelyRecogniseClassical( G, "linear" )

computes both a standard generating set for a matrix group G which contains the special linear group and expressions for the new generators in terms of G.generators. This generating set will allow you to write an element of G as a word in the given generating set of G.

The algorithm is of polynomial complexity in the dimension and field size. However, it is a Las Vegas algorithm, i.e. there is a chance that the algorithm fails to complete in the expected time. It will run indefinitely if G does not contain the special linear group.

The following functions can be applied to the record sl returned.

SizeFlag( sl )

returns the size of G.

Rewrite( sl, elm )

returns an expression such that Value( Rewrite( sl, elm ), G.generators ) is equal to the element elm.

Example

    gap> m1 := [ [ 0*Z(17), Z(17), Z(17)^10, Z(17)^12, Z(17)^2 ], 
      [ Z(17)^13, Z(17)^10, Z(17)^15, Z(17)^8, Z(17)^0 ], 
      [ Z(17)^10, Z(17)^6, Z(17)^9, Z(17)^8, Z(17)^10 ], 
      [ Z(17)^13, Z(17)^5, Z(17)^0, Z(17)^12, Z(17)^5 ], 
      [ Z(17)^14, Z(17)^13, Z(17)^5, Z(17)^10, Z(17)^0 ] ];;
    gap> m2 := [ [ 0*Z(17), Z(17)^10, Z(17)^2, 0*Z(17), Z(17)^10 ], 
      [ 0*Z(17), Z(17)^6, Z(17)^0, Z(17)^4, Z(17)^15 ], 
      [ Z(17)^7, Z(17)^6, Z(17)^10, Z(17), Z(17)^2 ], 
      [ Z(17)^3, Z(17)^10, Z(17)^5, Z(17)^4, Z(17)^6 ], 
      [ Z(17)^0, Z(17)^8, Z(17)^0, Z(17)^5, Z(17) ] ];;
    gap> G := Group( m1, m2 );;
    gap> sl := ConstructivelyRecogniseClassical( G, "linear" );;
    gap> SizeFlag(sl);
    338200968038818404584356577280
    gap> w := Rewrite( sl, m1^m2 );;
    gap> Value( w, [m1,m2] ) = m1^m2;
    true 

The algorithm is described in [4].

Previous Up Top Next
Index

GAP 3.4.4
April 1997