\documentclass[11pt]{article}
\usepackage{lslide}
\usepackage{path}
\usepackage{a4}
\usepackage{amsfonts}
\vertgroup
\landscape
\addtolength{\textheight}{0.27truein} % A4
\addtolength{\textwidth}{0.66truein} % A4
\parskip 1ex plus 1ex minus 0.2ex
\def\bs{\begin{slide}}
\def\es{\end{slide}}
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\GAP{\textsf{GAP}}
\begin{document}
\title[Computational Algebra]{Recent Developments in Computational
Algebra\\
\begingroup\Smallsize A Report from the Green Perspective\endgroup}
\author{Steve Linton}
\organization{Division of Computer Science, St.~Andrews}
\titlepage
\section{Introduction}
\bs
\subsection{Aims of Talk}
\bi
\item Report on Capabilities of Current Software
\item Illustrate Advantages of Integrated Systems
\item Focus on use for exploration by group theorists not specialising 
in computation
\ei
\es
\bs
\subsection{Overview}
\bi
\item Case Studies:
\bi
\item Constructing $HS$ from the number 23 -- Alexander Hulpke
\item Quotients of Grigorchuk's group -- Mike Newman
\ei
\item Quick overview of \GAP\ capabilities
\item New and forthcoming developments
\ei
\es
\section[Constructing $HS$]{Constructing $HS$ from the Number 23}
\bs
\subsection{Polynomials}

\bi
\item We begin with polynomials. Defining an
indeterminate gives us $\mathbb{F}_2[x]$
\begin{verbatim}
gap> x:=Indeterminate(GF(2));
X(GF(2))
gap> x.name:="x";;
\end{verbatim}
\item Now we can work with this:
\begin{verbatim}
gap> f:=x^23-1;
Z(2)^0*(x^23 + 1)
gap> Factors(f);
[ Z(2)^0*(x + 1), Z(2)^0*(x^11 + x^10 + x^6 + x^5 + x^
  4 + x^2 + 1), Z(2)^0*(x^11 + x^9 + x^7 + x^6 + x^
  5 + x + 1) ]
gap> f:=First(Factors(f),i->Degree(i)>1);
Z(2)^0*(x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1)
\end{verbatim}
\ei
\es
\bs
\subsection{A Code}

\bi
\item We next define a code, using the contributed package
\texttt{GUAVA}
\begin{verbatim}
gap> RequirePackage("guava");
   ___________                   |                  
  /            \           /   --+--  Version 1.3   
 /      |    | |\\        //|    |                  
|    _  |    | | \\      // |                        
|     \ |    | |--\\    //--|     Jasper Cramwinckel  
 \     ||    | |   \\  //   |     Erik Roijackers     
  \___/  \___/ |    \\//    |     Reinald Baart       
  				  Eric Minkes       
gap> cod:=GeneratorPolCode(f,23,GF(2));
a cyclic [23,12,1..7]3 code defined by generator 
polynomial over GF(2)
\end{verbatim}
\ei
\es
\bs
\subsection{Code 2}
\bi
\item This is the binary Golay code, we check a well-known property:
\begin{verbatim}
gap> IsPerfectCode(cod);
true
\end{verbatim}
\item Adding a parity bit gives us a code with automorphism group
$M_{24}$
\begin{verbatim}
gap> ext:=ExtendedCode(cod);
a linear [24,12,8]4 extended code
gap> WeightDistribution(ext);
[ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 
  759, 0, 0, 0, 0, 0, 0, 0, 1 ]
\end{verbatim}
\ei
\es
\bs
\subsection{The Group $M_{24}$}

GUAVA uses an external program to compute automorphism groups
quickly
\begingroup
\Smallsize
\begin{verbatim}
gap> m24:=AutomorphismGroup(ext); m24.name:="m24";;
Group( ( 1, 2)( 6,15,24,18)( 7,14,12,19)( 9,17,16,20)
(10,21,23,22)(11,13), ( 2, 3)( 6,10)( 7,24)( 9,17)(11,13)
(12,18)(14,21)(15,23), ( 3, 4)( 7,19)(10,22)(11,13)(12,14)
(15,18)(17,20)(21,23), ( 4, 5)( 6,23,21,16)( 7, 9,20,10)
(11,13)(12,15,17,19)(14,22,18,24), ( 5, 9,11,17)
( 6,19,24,21)( 7,23)( 8,20,13,16)(10,12)(14,15,22,18), 
( 5, 8)( 7,23)( 9,16)(10,12)(11,13)(14,22)(17,20)(19,21), 
( 6,10,19)( 7,14,18)( 8,11,13)( 9,17,16)(12,21,24)
(15,23,22), ( 6,19)( 7, 9)(10,20)(12,16)(14,24)(15,21)
(17,23)(18,22), ( 6, 7)( 9,19)(10,15)(12,24)(14,16)(17,22)
(18,23)(20,21), ( 6,18)( 7,23)( 9,17)(10,12)(14,21)(15,24)
(16,20)(19,22), ( 6,15)( 7,10)( 9,20)(12,23)(14,22)(16,17)
(18,24)(19,21) )
\end{verbatim}
\Large
\begin{verbatim}
gap> Size(m24);
244823040
\end{verbatim}
\endgroup
\es
\bs
\subsection{The Group $M_{22}$}

 $M_{22}.2$ is a two-set stabilizer in $M_{24}$
\begin{verbatim}
gap> m22a:=Stabilizer(m24,[23,24],OnSets);;
gap> Size(m22a);
887040
gap> m22a:=Operation(m22a,[1..22]);
Group( ( 1, 3)( 5,17)( 6,18)( 7,10)( 8,16)( 9,13)(11,20)
(21,22), ( 3, 4)( 5,13)( 6,15)( 7,10)( 9,21)(14,16)(17,22)
(19,20), ( 1, 2)( 6,15)( 7,10)( 8,11)( 9,19)(14,17)(16,22)
(20,21), ( 4,16)( 6,21)( 7,19)( 8,12)( 9,20)(10,15)(11,18)
(13,22), ( 1, 2)( 6, 7)( 8,11)( 9,20)(10,15)(12,18)
(19,21) )
\end{verbatim}
\es
\bs
\subsection{Towards The Higman-Sims Graph}

\Underbar{A Touch of Theory}

\bi
\item We know that $HS$ acts on a graph with $M_{22}.2$ as point stabilizer, and 
suborbit sizes 1,22 and 77.
\item We need an orbit on 77 points. The ATLAS tells us that $M_22$
has a maximal subgroup:
\begin{verbatim}
Order   Index  Structure  G.2       Abstract   Mathieu
 5760      77  2^4:A_6    2^4:S_6   N(2A^4)    hexad
\end{verbatim}
\item So this our action, with point stabilizer $H = 2^4:S_6$
\item $H$ contains a Sylow 2 subgroup of $M_{22}.2$, which must
have a normal subgroup $E = 2^4$
\item This will be our route to finding $H$
\ei
\es
\bs
\subsection{Finding $E$}
\bi 
\item A Sylow 2 subgroup is polycyclic, so we can use fast methods:
\begin{verbatim}
gap> s:=SylowSubgroup(m22a,2);;
gap> a:=AgGroup(s);
Group( g1, g2, g3, g4, g5, g6, g7, g8 )
gap> n:=Filtered(NormalSubgroups(a),i->Size(i)=16
>         and IsElementaryAbelian(i));;
gap> n[1];
Subgroup( Group( g1, g2, g3, g4, g5, g6, g7, g8 ), 
    [ g1, g3, g6*g7, g8 ] )
\end{verbatim}
\item Now we change back to permutations:
\begin{verbatim}
gap> n:=List(n,i->Image(a.bijection,i));;
\end{verbatim}
\item Finally, we happen to know that $E$ is regular:
\begin{verbatim}
gap> e:=First(n,i->IsRegular(i,PermGroupOps.MovedPoints(i)));;
\end{verbatim}
\ei
\es
\bs
\subsection{Making the 77 Point Action}
\bi
\item We make $H$ and then act on its cosets:
\begin{verbatim}
gap> h:=Normalizer(m22a,e);;
gap> mop:=Operation(m22a,RightCosets(m22a,h),OnRight);;
gap> DegreeOperation(mop,[1..100]);
77
gap> ophom:=OperationHomomorphism(m22a,mop);;
\end{verbatim}
\item \texttt{ophom} is the link between the 22 and 77 point actions
\ei
\es
\bs
\subsection{The 100 point action}

We combine the 22 and 77 point actions:
\begin{verbatim}
gap> dp:=DirectProduct(m22a,mop);;
gap> emb1:=Embedding(m22a,dp,1);;
gap> emb2:=Embedding(mop,dp,2);;
gap> diag:=List(m22a.generators,
>            i->Image(emb1,i)*Image(emb2,Image(ophom,i)));;
gap> diag:=Group(diag,());;
gap> diag.name:="M22.2-99";
\end{verbatim}

We can simply regard 100 as the fixed point.
\es
\bs
\subsection{Now the Higman-Sims Graph}

\bi
\item We use another contributed package 
\begin{verbatim}
gap> RequirePackage("grape");

Loading  GRAPE 2.31  (GRaph Algorithms using PErmutation groups),
by L.H.Soicher@qmw.ac.uk.
\end{verbatim}
\item GRAPE works with graphs, making maximum use of
known automorphisms. 
We start with an empty graph on which $M_{22}.2$ acts and adjoin edge
orbits
\ei
\es
\bs
\begingroup
\Smallsize
\begin{verbatim}
gap> gamma:=NullGraph(diag,100);
rec(
  isGraph := true,
  order := 100,
  group := M22.2-diag,
  schreierVector := 
   [ -1, 3, 1, 2, 1, 4, 5, 1, 2, 4, 3, 4, 4, 2, 2, 4, 3, 
      4, 5, 1, 1, 3, -2, 5, 4, 1, 5, 5, 4, 2, 4, 4, 3, 4, 
      4, 2, 3, 4, 1, 4, 5, 1, 4, 2, 2, 3, 1, 5, 1, 5, 4, 
      2, 2, 2, 5, 2, 5, 3, 3, 4, 5, 3, 5, 2, 5, 3, 3, 1, 
      3, 4, 1, 3, 1, 1, 1, 4, 1, 4, 3, 5, 5, 5, 3, 3, 3, 
      1, 2, 4, 4, 4, 2, 2, 2, 4, 1, 1, 1, 1, 2, -3 ],
  adjacencies := [ [  ], [  ], [  ] ],
  representatives := [ 1, 23, 100 ],
  isSimple := true )
\end{verbatim}
\endgroup
\es
\bs
\subsection{Building up the graph 1}
\bi
\item First connect the point 100 to the orbit of size 22
\begin{verbatim}
gap> AddEdgeOrbit(gamma,[1,100]);AddEdgeOrbit(gamma,[100,1]);
\end{verbatim}
\item The ATLAS tell us:
\begin{quote}
each of the remaining 77 vertices is joined to 6 of these [the 22]
points, and may be labelled by the corresponding hexad
\end{quote}
\item We find the hexad fixed by $H$  and make these edges:
\begin{verbatim}
gap> hexad:=First(Orbits(h,[1..22]),i->Length(i)=6);
[ 1, 13, 15, 18, 17, 19 ]
gap> AddEdgeOrbit(gamma,[hexad[1],23]); 
gap> AddEdgeOrbit(gamma,[23,hexad[1]]); 
\end{verbatim}
\ei
\es
\bs
\subsection{Building up the Graph 2}
\bi
\item There are also edges within the size 77 orbit:
\begin{quote}
Two of these 77 vertices are joined just if the corresponding hexads
are disjoint.
\end{quote}
\begin{verbatim}
gap> stab := Stabilizer(diag,23);;
gap> orbs := Orbits(stab,[24..99]);;
gap> orbreps := List(orbs,o->o[1]);
[ 24, 43 ]
gap> Intersection(hexad, Adjacency(gamma, 24));
[ 1, 13 ]
gap> Intersection(hexad, Adjacency(gamma, 43));
[ ]
gap> AddEdgeOrbit(gamma,[23,43]); AddEdgeOrbit(gamma,[43,23]);
\end{verbatim}
\item Now we have made the graph we want
\ei
\es
\bs
\subsection{Checking the Graph}
\bi
\item We can look at a few properties:
\begin{verbatim}
gap> IsSimpleGraph(gamma);
true
gap> Adjacency(gamma,23);
[ 1, 13, 15, 17, 18, 19, 43, 44, 47, 48, 59, 61, 70, 71, 
  76, 77, 82, 84, 88, 90, 92, 94 ]
gap> IsDistanceRegular(gamma);
true
\end{verbatim}
\ei
\es
\bs
\subsection{At Last the Higman-Sims Group}

\bi
\item Finally, we take the automorphism group of \texttt{gamma}. Once
again an external program is used, but we don't see it:
\begin{verbatim}
gap> aug:=AutGroupGraph(gamma);;
gap> Size(aug);
88704000
gap> DisplayCompositionSeries(aug);
(G) (3 gens, size 88704000)
 | Z(2)
(S) (2 gens, size 44352000)
 | HS
(1) (0 gens)
\end{verbatim}
\ei
\es
\bs
\subsection{Summary}
\bi
\item From a polynomial factoring over $\mathbb{F}_2$ we get a code
\item From the code, we get $M_{24}$ and hence $M_{22}:2$
\item In $M_{22}:2$ on 22 points, we find a subgroup of index 77
\item We construct a 100 point graph on which $M_{22}:2$ acts
\item The full automorphism group is $HS:2$
\ei
\es
\bs
\subsection{Points to Note}
\bi
\item We have turned a piece of mathematics relatively painlessly 
into a program
\item At every stage, the full structure of all the objects is
exposed. We can ask \GAP\ questions about each code, graph or group.
\item The whole thing runs in 45 seconds on a Pentium 90 laptop
\item We have combined techniques from a number of areas
\item \GAP\ provided common interfaces and data structures for them
all
\item A little extra knowledge, of the problem and of \GAP\ helps
\ei
\es
\section{Quotients of Grigorchuk's Group}
\bs
\subsection{The Problem}
\bi
\item A group $G_r$ is defined by an action on a homogeneous tree
\item Finite quotients are obtained by considering only the action on
the top few levels of the tree
\item We wish to study these, and their normal and characteristic
subgroups
\ei
\es
\bs
\subsection{The Approach}
\bi
\item We write short programs to do the (truncated) construction
\item Then we explore the groups interactively
\item This hybrid of programming and interaction is 
a very common way of working with \GAP.
\ei
\es
\bs
\subsection{Programming the Construction}
\bi
\item $G_r$ is generated by two kinds of elements
\item One generator permutes the branches directly below the root
\item Others fix a ``spine'' and permute other subtrees according to a 
repeating pattern
\item We write \GAP\ functions to compute these to a specified level,
taking as input the shape of the tree and the patterns of permutations
\item Various input checks are omitted for brevity
\ei
\es
\bs
\subsection{The Program for the Top level permutation}
\begingroup
\Smallsize
\begin{verbatim}
# The element (usually called a) that acts at the root
# nbar is the tree shape, perm the top level permutation
# level is the amount of tree to look at

TopElement := function(nbar, perm, level) 
    local blocksize,ims,n1;
    if IsInt(nbar) then
        nbar := List([1..level],x->nbar);
    fi;
    n1 := nbar[1];
    blocksize := Product(nbar{[2..Length(nbar)]});
    ims := Concatenation(List([1..n1], 
        i-> [(i^perm - 1)*blocksize + 1 .. i^perm*blocksize]));
    return PermList(ims);
end;
\end{verbatim}
\endgroup
\es
\bs
\subsection{The Program for the Other Generators}
\begingroup
\Smallsize
\begin{verbatim}
SequenceElement := function(nbar, seq, level)
    local ims,i,blocksize,n,x,perms,offset;
    offset := 0;    ims := [];
    if IsInt(nbar) then
        nbar := List([1..level],i->nbar);
    fi;
    blocksize := Product(nbar{[2..Length(nbar)]});
    for i in [1..level-1] do
        n := nbar[i+1]; blocksize := blocksize/n;
        perms := seq[(i -1) mod Length(seq) +1];
        if not IsList(perms) then perms := [perms]; fi;
        for x in perms do
            Append(ims,Concatenation(List([1..n],
                    i-> offset + [(i^x - 1)*blocksize + 1 .. i^x*blocksize])));
            offset := offset + n*blocksize;
    od; od;
    Add(ims,offset+1);
    return PermList(ims);
end;
\end{verbatim}
\endgroup    
\es
\bs
\subsection{Programs to Make the Group We Want}
\bi
\item Now we add a few lines to make the generators of the specific
group we want
\begin{verbatim}
GenA := level -> TopElement(2,(1,2),level);
GenB := level -> SequenceElement(2,[(1,2),(1,2),()],level);
GenC := level -> SequenceElement(2,[(1,2),(),(1,2)],level);

MakeGroup := level->Group(GenA(level),GenB(level),GenC(level));
\end{verbatim}
\item We put these in a file and try them out
\begingroup
\Smallsize
\begin{verbatim}
gap> Read("grigor.g");
gap> MakeGroup(5);
Group( ( 1,17)( 2,18)( 3,19)( 4,20)( 5,21)( 6,22)( 7,23)( 8,24)( 9,25)(10,26)
(11,27)(12,28)(13,29)(14,30)(15,31)(16,32), ( 1, 9)( 2,10)( 3,11)( 4,12)
( 5,13)( 6,14)( 7,15)( 8,16)(17,21)(18,22)(19,23)(20,24)(29,30), ( 1, 9)
( 2,10)( 3,11)( 4,12)( 5,13)( 6,14)( 7,15)( 8,16)(25,27)(26,28)(29,30) )
gap> g := last;; Size(g);
4194304
gap> Collected(Factors(last));
[ [ 2, 22 ] ]
\end{verbatim}
\endgroup
\ei
\es
\bs
\subsection{Analysing the Group 1}
\bi
\item Since this group actually is soluble, it will be more efficient
to treat it as such
\begin{verbatim}
gap> a := AgGroup(g);
Group( g1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11, g12, 
g13, g14, g15, g16, g17, g18, g19, g20, g21, g22 )
\end{verbatim}
\item Now we can compute all the normal subgroups -- this takes an
hour or so
\begin{verbatim}
gap> ns := NormalSubgroups(a);;
gap> Length(ns);                                                             
77
\end{verbatim}
\ei
\es
\bs
\subsection{Analysing 2}
\bi
\item Now we wish to know which are characteristic
\item We use the ANU pq share package to compute generators for the
automorphism group of \texttt{g}.
\begin{verbatim}
gap> RequirePackage("anupq");
gap> ag := AutomorphismsPGroup(a);;
gap> Length(ag);  # generators                                                            
29
\end{verbatim}
\item Finally we check which of our 77 normal subgroups are not
characteristic
\begin{verbatim}
gap> Filtered([1..77],i->not ForAll(ag,phi->ForAll(ns[i].generators,           
> x->Image(phi,x) in ns[i])));
[  ]
\end{verbatim}
\item So they all are
\ei
\es
\bs
\subsection{Points to Note}
\bi
\item We used basically standard $p$-group tools for the hard jobs
\item But \GAP\ makes it easy to prepare input and analyse results
flexibly
\item We programmed the fiddly construction but did the analysis
interactively
\item In \GAP\ 4 we could do the whole calculation with the
permutation group, using $p$-group methods 
\ei
\es
\section[Conclusions]{Concluding Remarks}
\bs
\subsection{What can be done}

With a little patience, on a large PC, in \GAP\ or MAGMA:
\bi
\item Permutation groups up to degree $10^6$ for many purposes
\item Backtrack searching (centralizer etc.) up to degree $10^5$ in
many cases
\item Conjugacy classes and double cosets are much harder
\item Nilpotent groups with $\log|G|$ up to $10^3$ for many purposes
\item Soluble groups a little smaller
\item Computation with words in free generators
\item Various techniques for exploring quotients of finitely-presented 
groups
\item Modular representations up to dimension $10^3$ (more by indirect 
routes)
\item Character and modular character table constructions
\item and more
\ei
\es
\bs

\subsection{References}
\bi
\item An Introduction to Computational Group Theory, Akos Seress, 
Notices of the AMS 44, no 6, June/July 1997, pp 671--679
\item An Invitation to Computational Group Theory, Joachim Neub\"user, 
Proceedings of ``Groups '93 Galway/St Andrews'', LMS Lecture Note
Series 212, pp 457--475
\item \path|http://www-gap.dcs.st-and.ac.uk/~gap|
\ei
\es
\bs
\subsection{Contributed ``Share'' Packages}
\bi
\item Increasingly important part of \GAP
\item User contributed and supported
\item Some links to stand-alone programs -- \texttt{nauty},
\texttt{anupq}, vector enumerator, C meataxe
\item Some pure \GAP\ -- CHEVIE, Specht, \texttt{autag}, chrystgap,
GRAPE (almost), \texttt{grim}, crossed module package, \texttt{matrix}
\item Package refereeing system
\item Full details on the Web pages
\ei
\es
\bs
\subsection{Recent Developments (some due shortly)}

\Underbar{Groups}
\bi
\item Matrix groups -- as discussed last week 
\item Nearly-linear time permutation groups library
\item Partition backtrack methods for many problems
\item Hybrid methods for soluble permutation or matrix groups
\item Polycyclic quotient algorithm
\item Methods for infinite nilpotent groups, based on Hall polynomials 
and Deep Thought
\ei
\es
\bs
\subsection{More Recent Developments}

\Underbar{Algebraic Broadening}
\bi
\item Algorithms and implementations
for other algebraic structures have been much less sophisticated than those for groups
\item  New methods and code for semigroups and 
Lie algebras inspired by group theoretic methods
\item These can be used to shed light on groups, or in their own right
\item The latest methods in computational representation theory also
use deep theory and a broad range of computational components
\ei

\Underbar{General Things}
\bi
\item A (somewhat) more careful attitude to randomness -- coming from
the red perspective
\item A general move from stand-alone programs to integrated systems
\item A growth in databases providing high-quality access to the
results of various classification efforts
\ei
\es
\bs
\subsection{Finally}
\bi
\item Reasonably easy-to-use computational tools now exist for
investigations in a broad and growing range of algebraic areas
\item Last week we saw a few of the topics in computational algebra
that are alive and blooming
\item I should like to repeat Joachim Neub\"user's 1993 ``Invitation
to Computational Group Theory'', rephrased -- ``come on in, 
the water's lovely''
\item If you do use \GAP\ please tell us, and cite the \GAP\ manual
\item If you develop applications, consider making them generally available
\ei
\es
\end{document}






