Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

561421 views
����;� TeX output 2010.02.16:1144����������p���ww����_�<p��i(
cmssdc10�AutPGrp�� �<���|��"���`REA���GAP4�P����ack�age��n鍒�ɢ�>p��i
cmssdc10�b��ly��i�����=0Bettina�n�Eick�and�Eamonn�O'Brien��h�[��¿FF��leb�rua�ry�n�2010�����*�����p����E����FK��Contents����N������@��"V

cmbx10�1���$In��9tro�Q�duction���j��3������������@2���$The��Tautomorphism�group�metho�Q�d������4������������@3���$The��Tunderlying�function���/��6������������@4���$In
uencing��Tthe�algorithm���*)8������������8��K�`y

cmr10�4.1���$Outline�UUof�the�algorithm�
���r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.������8������������8�4.2���$The�UUinitialisation�step�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.������9������������8�4.3���$Stabilisers�UUin�matrix�groups�
ꚍ��r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.������9������������8�4.4���$Searc���hing�UUfor�a�small�generating�set������r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.������10������������8�4.5���$An�UUin���teractiv�e�v�ersion�of�the�algorithm�	�@���r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.������10������������8�4.6���$Ac���kno�wledgemen�ts�
q����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.�����r.������11������������@�5���$Additional��TF��
�eatures�of�the�P��9ac�k��\rage�����12���������7�����p����E����j)�;�>a�h�h�cminch�1����2�Intro�7duction����8N8��Giv���en�an�arbitrary�nite�group,�the�computation�of�its�automorphism�group�is�a�v���ery�dicult�task.�Pioneer���w���ork���in�this�area�w�as�carried�out�b�y�F��*�elsc�h���&�Neub�G����user�(1970),�whose�algorithm�used�the�output�of�their���subgroup�Ulattice�Tprogram.�A�#tec���hnique�dev�elop�Ged�b�y�TNeub�G����user�in�the�early�1970s�sough���t�to�compute�the���automorphism�3group�2view���ed�as�a�p�Germ�utation�2group�acting�on�unions�of�certain�conjugacy�classes�of�the���group.��5A��similar�metho�Gd��4w���as�implemen�ted�b�y�Hulpk�e�(1997)��4in�the��m#�R

cmss10�GAP��4�library��*�.�Recen�tly��*�,��4Cannon�&�Holt���(1999)�UUpresen���ted�a�new�algorithm�whic�h�uses�a�\h�ybrid�group"�approac�h.��N8�More���ecien���t���approac�hes�are�a�v��q�ailable���to�determine�the�automorphism�group�for�groups�satisfying�certain���prop�Gerties.��EF��*�ollo���wing��Fthe�w�ork��Fof�Sho�Gda�(1928),�Hulpk���e�in�1997�implemen���ted�a�practical�metho�Gd�for�nite���ab�Gelian�W6groups�in�the�W7�GAP��4�library��*�.�W�ursthorn�(1993)�adapted�mo�Gdular�group�W7algebra�tec���hniques�to�compute���the��automorphism�groups�of��$�':

cmti10�p����-groups;�the��GAP��3��share�pac���k��q�age��Sisyphos��includes�an�implemen�tation.�Smith���(1994)���in���tro�Gduced���an�algorithm�for�nite�solv��q�able�groups�whic���h�is�a���v��q�ailable�in�the��AutAg��share�pac���k��q�age�of����GAP�UU�3.���Moreo���v�er,�wthe��p����-group�generation�wmetho�Gd�of�Newman�(1977)�and�O'Brien�(1990)�can�b�Ge�mo�died�to�compute���the��vautomorphism��wgroup�of�a�nite��p����-group�as�outlined�in�O'Brien�(1995).�This�algorithm�is�implemen���ted���in�UUthe�ANU����<x

cmtt10�pq��C�program.���Here�V�w���e�V�in�tro�Gduce�a�new�V�function�to�compute�the�automorphism�group�of�a�nite��p����-group.�The�underlying���algorithm�Jjis�Jia�renemen���t�of�the�metho�Gds�describ�ed�Jiin�O'Brien�(1995).�In�particular,�this�implemen���tation�is���more��ecien���t�in�b�Goth�time�and�space�requiremen�ts�and��hence�has�a�wider�range�of�applications�than�the���ANU��Q�pq��f�metho�Gd.��eOur�pac���k��q�age�is�written�in��GAP��Q�co�Gde�and�it�mak���es�use�of�a�n���um�b�Ger��fof�metho�ds��ffrom�the����GAP�UU�library�suc���h�as�the�MeatAxe�for�matrix�groups�and�p�Germ�utation�group�functions.���The�|оGAP�|ϫ4�pac���k��q�age��ANUPQ�,�whic�h�|�is�an�in�terface�|�to�most�of�the�functionalit���y�of�the�ANU�|��pq��C�program,���uses�UUthe��AutPGrp��pac���k��q�age�to�compute�automorphism�groups�of��p����-groups.���W��*�e��ha���v�e��compared�our�metho�Gd�to�the�others�a���v��q�ailable�in��GAP�.�Our�pac���k��q�age�usually�out-p�Gerforms�all�but���the���metho�Gd�designed���for�nite�ab�elian�groups.���W��*�e�note�that�our�metho�Gd�uses�the�small�groups�library�in���certain�UUcases�and�hence�our�algorithm�is�more�eectiv���e�if�the�small�groups�library�is�installed.���A�UU�GAP��3�v���ersion�of�the�metho�Gds�implemen�ted�in�this�pac�k��q�age�is�a�v��q�ailable�via�����9��http://www-public.tu-bs.de:8080/~beick/so.html������������p����E����j)�2�������~��The��automo����rphism��,����group�Cmetho�7d����;x㍫The�8�AutPGrp��pac���k��q�age�installs�a�metho�Gd�for��AutomorphismGroup��for�a�nite��p����-group�(see�also�Section�\ref:groups���
���of�UUautomorphisms"�in�the��GAP��Reference�Man���ual).��������|{Ycmr8�1������L�3�u�7msam7�I���AutomorphismGroup(�?��G�F�)�S�۫M��N8�The�T�input�T�is�a�nite��p����-group��G��I�.�If�the�lters��IsPGroup�,��IsFinite��and��CanEasilyComputePcgs��are�set�and���true�UUfor��G��I�,�the�metho�Gd�selection�of��GAP��4�in���v�ok�es�UUthis�algorithm.��N8�The�pAoutput�pBof�the�metho�Gd�is�an�automorphism�group,�whose�generators�are�giv���en�in��GroupHomomorphism-���ByImages�UU�format�in�terms�of�their�action�on�the�underlying�group��G��I�.��������2������L�I���InfoAutGrp���V��N8�This��is�a��GAP�z�InfoClass�(these�are�describ�Ged�in��Chapter�\ref:info�functions"�in�the��GAP��Reference�Man���ual).���By�UUassigning�an��info-level�]ޫin�the�range�1�to�4�via����9��SetInfoLevel(InfoAutGrp,�?��info-level���)��N8��v��q�arying�UUlev���els�of�information�on�the�progress�of�the�computation,�will�b�Ge�obtained.����9��gap>�?�RequirePackage("autpgrp");����9�#I�?�------------�The�AutPGrp�package�--------------����9�#I�?�--�Computing�automorphism�groups�of�p-groups�--����9�true����9�gap>�?�G�:=�SmallGroup(�32,�15�);����9�<pc�?�group�of�size�32�with�5�generators>����9�gap>�?�SetInfoLevel(�InfoAutGrp,�1�);����9�gap>�?�AutomorphismGroup(G);����9�#I�
�step�?�1:�2^2�--�init�automorphisms����9�#I�
�step�?�2:�2^2�--�aut�grp�has�size�2����9�#I�
�step�?�3:�2^1�--�aut�grp�has�size�32����9�#I�
�final�?�step:�convert����9�<group�?�of�size�64�with�6�generators>��N8��The�5�algorithm�pro�Gceeds�b���y�5�induction�do�wn�the�lo�w�er��p����-cen�tral�series�of��G���and�the�information�corresp�Gonds���to��
the�steps��	of�this�induction.�In�the�follo���wing�example�w�e��	observ�e�that�the�metho�Gd��	also�accepts�p�erm���utation���groups�UUas�input,�pro���vided�they�satisfy�the�required�lters.���������������5���p������9��gap>�?�G�:=�DihedralGroup(�IsPermGroup,�2^5�);����9�Group([�?�(�1,�2,�3,�4,�5,�6,�7,�8,�9,10,11,12,13,14,15,16),������(�?�2,16)(�3,15)(�4,14)(�5,13)(�6,12)(�7,11)(�8,10)�])����9�gap>�?�IsPGroup(G);����9�true����9�gap>�?�CanEasilyComputePcgs(G);����9�true����9�gap>�?�IsFinite(G);����9�true����9�gap>�?�AutomorphismGroup(G);����9�#I�
�step�?�1:�2^2�--�init�automorphisms����9�#I�
�step�?�2:�2^1�--�aut�grp�has�size�2����9�#I�
�step�?�3:�2^1�--�aut�grp�has�size�8����9�#I�
�step�?�4:�2^1�--�aut�grp�has�size�32����9�#I�
�final�?�step:�convert����9�<group�?�of�size�128�with�7�generators>����9�gap>�?�A�:=�last;;����9�gap>�?�A.1;����9�Pcgs([�?�(�2,16)(�3,15)(�4,14)(�5,13)(�6,12)(�7,11)(�8,10),������(�?�1,�2,�3,�4,�5,�6,�7,�8,�9,10,11,12,13,14,15,16),������(�?�1,�3,�5,�7,�9,11,13,15)(�2,�4,�6,�8,10,12,14,16),������(�?�1,�5,�9,13)(�2,�6,10,14)(�3,�7,11,15)(�4,�8,12,16),������(�?�1,�9)(�2,10)(�3,11)(�4,12)(�5,13)(�6,14)(�7,15)(�8,16)�])�->����9�[�?�(�1,�2)(�3,16)(�4,15)(�5,14)(�6,13)(�7,12)(�8,11)(�9,10),������(�?�1,�2,�3,�4,�5,�6,�7,�8,�9,10,11,12,13,14,15,16),������(�?�1,�3,�5,�7,�9,11,13,15)(�2,�4,�6,�8,10,12,14,16),������(�?�1,�5,�9,13)(�2,�6,10,14)(�3,�7,11,15)(�4,�8,12,16),������(�?�1,�9)(�2,10)(�3,11)(�4,12)(�5,13)(�6,14)(�7,15)(�8,16)�]����9�gap>�?�Order(A.1);����9�16�����%�����p����E����j)�3����Z~�The���underlying���function����:ꪍ�Underlying���the���metho�Gd�installation�for��AutomorphismGroup��is�the�function��AutomorphismGroupPGroup�.���This���function�is�in���tended�for���exp�Gert�users�who�wish�to�in
uence�the�steps�of�the�algorithm.�Note�also�that����AutomorphismGroup�UU�will�alw���a�ys�UUc�ho�Gose�default�v��q�alues.��������1������L�I���AutomorphismGroupPGroup(�?��G�F�[,�
ag��}�]�)��P�F��N8�The�#vinput�#uis�a�nite��p����-group�as�ab�Go���v�e�and�#van�optional��
ag��whic���h�can�b�Ge�true�or�false.�Here�the�lters�for��G����need�>�not�>�b�Ge�set,�but�they�should�b�Ge�true�for��G��I�.�The�p�Gossible�v��q�alues�for��
ag�!�are�considered�later�in�Chapter���4.�F$If��
ag�(��is�not�supplied,�the�algorithm�F%pro�Gceeds�similarly�to�the�metho�d�F%installed�for��AutomorphismGroup�,���but��it��pro�Gduces�sligh���tly�more�detailed�output.�The�output�of�the�function�is�a�record�whic���h�con�tains��the���follo���wing�UUelds:����glAutos����$�a�UUset�of�automorphisms�whic���h�together�with��agAutos��generate�the�automorphism�group;��N8��glOrder����$�an�UUin���teger�whose�pro�Gduct�with�the��agOrders��giv�es�the�size�of�the�automorphism�group;����agAutos����$�a�UUp�Golycyclic�generating�sequence�for�a�soluble�normal�subgroup�of�the�automorphism�group;����agOrder����$�the�UUrelativ���e�orders�corresp�Gonding�to��agAutos�;����one����$�the�UUiden���tit�y�elemen�t�of�the�automorphism�group;����group����$�the�UUunderlying�group��G��I�;����size����$�the�UUsize�of�the�automorphism�group.���p�W��*�e�&5do�&6not�return�an�automorphism�group�in�the�standard�form�b�Gecause�w���e�wish�to�distinguish�b�Get���w�een����agAutos�ϫand��glAutos�;�the�latter�act�non-trivially�on�the�F��*�rattini�quotien���t�of��G��I�.�This�h�ybrid-group�descrip-���tion���of��the�automorphism�group�p�Germits�more�ecien���t�computations�with�it.�The�follo���wing�function�con���v�erts���the�UUoutput�of��AutomorphismGroupPGroup��to�the�output�of��AutomorphismGroup�.��������2������L�I���ConvertHybridAutGroup(�?��A��)�B�A�F��N8��9��gap>�?�RequirePackage("autpgrp");����9�#I�?�------------�The�AutPGrp�package�--------------����9�#I�?�--�Computing�automorphism�groups�of�p-groups�--����9�true����9�gap>�?�H�:=�SmallGroup�(729,�34);����9�<pc�?�group�of�size�729�with�6�generators>�����#����������7���p������9��gap>�?�A�:=�AutomorphismGroupPGroup(H);����9�rec(�?�glAutos�:=�[�
�],����(y�glOrder�?�:=�1,����(y�agAutos�?�:=�[�Pcgs([�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1^2,�f2,�f3^2*f4,�f4,�f5^2*f6,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f2^2,�f1,�f3*f5^2,�f5^2,�f4*f6^2,�f6^2�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1^2,�f2^2,�f3*f4^2*f5^2*f6,�f4^2*f6,�f5^2*f6,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1*f3,�f2,�f3*f5^2,�f4*f6^2,�f5,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1,�f2*f3,�f3*f4,�f4,�f5*f6,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1*f4,�f2,�f3*f6^2,�f4,�f5,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1,�f2*f4,�f3,�f4,�f5,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1*f5,�f2,�f3,�f4,�f5,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1,�f2*f5,�f3*f6,�f4,�f5,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1*f6,�f2,�f3,�f4,�f5,�f6�],����l��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6�])����w9�->�?�[�f1,�f2*f6,�f3,�f4,�f5,�f6�]�],����(y�agOrder�?�:=�[�2,�2,�2,�3,�3,�3,�3,�3,�3,�3,�3�],����(y�one�?�:=�?�IdentityMapping(�<pc�group�of�size�729�with�6�generators>�),����(y�group���:=�?�<pc�group�of�size�729�with�6�generators>,����(y�size���:=�?�52488�)����9�gap>�?�ConvertHybridAutGroup(�A�);����9�<group�?�of�size�52488�with�11�generators>��N8��Let��O�A���b�Ge�the�automorphism�group��Nof�a��p����-group��G�ט�as�computed�b���y��AutomorphismGroupPGroup�.�Then���the�zfollo���wing�function�can�compute�a�p�Gc�group�isomorphic�to�the�solv��q�able�part�of��A�L�stored�in�the�record���comp�Gonen���t�aK�A�.agGroup.�aLThis�solv��q�able�part�forms�a�subgroup�of�the�automorphism�group�whic���h�con�tains���at�gleast�the�automorphisms�hcen���tralizing�the�F��*�rattini�factor�of��G��I�.�The�p�Gc�group�facilitates�v��q�arious�further���computations�UUwith��A�.��������3������L�I���PcGroupAutPGroup(�?��A��)�]
2�F��N8�computes�C6a�p�Gc�presen���tation�for�the�solv��q�able�part�of�the�automorphism�group��A�C2�dened�b�y��A�.agGroup.��A�C1�is���the�UUoutput�of�the�function��AutomorphismGroupPGroup�.����9��gap>�?�H�:=�SmallGroup�(729,�34);;����9�gap>�?�A�:=�AutomorphismGroupPGroup(H);;����9�gap>�?�B�:=�PcGroupAutPGroup(�A�);����9�<pc�?�group�of�size�52488�with�11�generators>����9�gap>�?�I�:=�InnerAutGroupPGroup(�B�);����9�Group([�?�f5,�f4^2*f8,�f6^2*f9^2,�f11^2,�f10^2,�<identity>�of�...�])�����-f�����p����E����j)�4������(��In
uencing��,����the�n
algo����rithm����:ꪍ�A�nqn���um�b�Ger�nxof�c���hoices�can�b�e�made�b���y�the�user�to�nwin
uence�the�p�erformance�of��AutomorphismGroupPGroup�.���Belo���w���w�e�iden�tify�these�c�hoices�and�their�default�v��q�alues�used�in��AutomorphismGroup�.�W��*�e�use�the�optional���argumen���t���
ag��7�of��AutomorphismGroupPGroup��to��in�v�ok�e�user-dened�c�hoices.�The��p�Gossible�v��q�alues�for��
ag��8�are��N8��
ag�"z�=�?�false����$�the�UUuser-dened�defaults�are�emplo���y�ed�UUin�the�algorithm.�See�b�Gelo���w�for�a�list�of�p�ossibilities.��N8��
ag�"z�=�?�true����$�in���v�ok�es�UUthe�in���teractiv�e�UUv�ersion�of�the�algorithm�as�describ�Ged�in�Section�4.5.���p�In�ױthe�next�section�w���e�ײgiv�e�ױa�brief�outline�of�the�algorithm�whic���h�is�necessary�to�understand�the�p�Gossible���c���hoices.�UUThen�w�e�in�tro�Gduce�the�c�hoices�the�later�sections�of�this�c�hapter.��N8��4.1��`Outline�n�of�the�algo��lrithm��N8��The��*basic�algorithm��+pro�Gceeds�b���y�induction�do�wn�the�lo�w�er��+�p����-cen�tral�series�of�a�giv�en��p����-group��+�G��I�;�that�is,���it�Y'successiv���ely�computes�Y&�A���ut��ث(�G����@�':
cmti10�@i��\$�)�for�the�quotien�ts��G����@i��)��=��v�G��I��b>

cmmi10�=�P����@i��\$�(�G��)�Y'of�the�descending�Y&sequence�of�subgroups���dened��b���y���P����ٓ�Rcmr7�1��|s�(�G��I�)�y�=��G����and��P����@i����+1��
|'�(�G��I�)�y�=�[�P����@i��\$�(�G��)�;����G��]�P����@i���(�G��)���^��@p��	x��for���i�~��!",�

cmsy10��y��1.�Hence,��in�the�initial�step�of�the���algorithm,�ʎ�A���ut��ث(�G����2��|s�)��w=��GL�(�d���;����p����)�ʏwhere��d���is�the�rank�of�the�elemen���tary�ab�Gelian�group��G����2��|s�.�In�the�inductiv���e���step��Sit��Rdetermines��A���ut��ث(�G����@i����+1��
|'�)�from��A���ut��ث(�G����@i��\$�).�F��*�or�this�purp�Gose�w���e�in�tro�Gduce��Ran�action�of��A���ut��ث(�G����@i��\$�)�on�a�certain���elemen���tary�	�ab�Gelian��p����-group��M����(the��p��-m��9ultiplicator��of��G����@i��\$�).�The�main�computation�of�the�inductiv���e�step�is���the�WRdetermination�of�the�stabiliser�in��A���ut��ث(�G����@i��\$�)�of�a�subgroup��U���of��M��(the��allo��9w�able�םsubgroup�WR�for��G����@i����+1��
|'�).���This�UUstabiliser�calculation�is�the�b�Gottle-nec���k�of�the�algorithm.���Our�pac���k��q�age�incorp�Gorates�a�n���um�b�Ger�of�renemen�ts�designed�to�simplify�this�stabiliser�computation.�Some�of���these���renemen���ts���incur�o�v�erheads�and�hence���they�are�not�alw�a�ys���in�v�ok�ed.�The�features�outlined���b�Gelo�w�allo�w���the�UUuser�to�select�them.���Observ���e�Nthat�the�initial�step�of�the�algorithm�returns�O�GL�(�d���;����p����).�But��A���ut��ث(�G��I�)�ma�y�induce�on��G����2��~��a�prop�Ger���subgroup,�K�sa���y�K��K�s�,�of��GL�(�d���;����p����).�An�y�K�in�termediate�subgroup�of��GL�(�d���;����p����)�K�whic�h�con�tains��K��r�suces�K�for�the���algorithm�`~and�w���e�supply�t�w�o�metho�Gds�to�construct�`}a�suitable�subgroup:�these�use�c�haracteristic�subgroups���or�UUin���v��q�arian�ts�of�normal�subgroups�of��G��I�.�(See�Section�4.2.)���In�e�the�e�inductiv���e�step�an�action�of��A���ut��ث(�G����@i��\$�)�on�an�elemen���tary�ab�Gelian�group��M�	�is�used.�This�action�is�computed���as�]�a�matrix�action�on�a�v���ector�space.�T��*�o�simplify�the�orbit-stabiliser�computation�of�the�subspace��U�i�of��M����,���w���e�-�can�-�construct�the�stabiliser�of��U��y�b���y�iteration�o���v�er�a�-�sequence�of��A���ut��ث(�G����@i��\$�)-in���v��q�arian�t�subspaces�-�of��M����.�(See���Section�UU4.3.)���Orbit-stabiliser��rcomputations��qin�nite�solv��q�able�groups�giv���en�b�y��qa�p�Golycyclic�generating�sequence�are�m���uc�h���more�Secien���t�Sthan�generic�computations�of�this�t���yp�Ge.�Th�us�our�algorithm�Smak�es�use�of�Sa�large�solv��q�able���normal�#Usubgroup��S�Uҫof��A���ut��ث(�G����@i��\$�).�F��*�urther,�it�is�useful�if�the�generating�set�of��A�ut��ث(�G����@i��\$�)�outside��S�Uҫis�as�small�as���p�Gossible.���T��*�o���ac���hiev�e�this���w�e�determine�a���p�Germ�utation�represen�tation���of��A���ut��ث(�G����@i��\$�)�=�S�f�and�use�this�to�reduce���the�UUn���um�b�Ger�of�generators�if�p�ossible.�(See�Section�4.4.)�����	7������Se��}'ction���3.�Stabilisers�in�matrix�gr�oups�'��9���p������4.2��`The�n�initialisation�step��N8��Assume���w���e�seek���to�compute�the�automorphism�group�of�a��p����-group��G���ha���ving�F��*�rattini�rank��d���.�W��*�e�rst���determine�UUas�small�as�p�Gossible�a�subgroup�of��GL�(�d���;����p����)�whose�extension�can�act�on��G��I�.��N8�The�UUuser�can�c���ho�Gose�the�initialisation�routine�b�y�assigning��InitAutGroup��to�an�y�one�of�the�follo�wing.��N8��InitAutomorphismGroupOver����$�to�UUuse�the�minimal�o���v�ergroups;����InitAutomorphismGroupChar����$�to�UUuse�the�c���haracteristic�subgroups;����InitAutomorphismGroupFull����$�to�UUuse�the�full��GL�(�d���;����p����).���p��a)��TMinimal�Ov��9ergroups����W��*�e��$determine�the��%minimal�o���v�er-groups��$of�the�F��*�rattini�subgroup�of��G��n�and�compute�in���v��q�arian�ts��$of�these�whic���h���m���ust���b�Ge���resp�ected�b���y�the�automorphism���group�of��G��I�.�W��*�e�partition�the�minimal�o���v�ergroups���and�compute�the���stabiliser�UUin��GL�(�d���;����p����)�of�this�partition.���The���partition���of�the�minimal�o���v�ergroups�is���computed�using�the�function��PGFingerprint(�?�G,�U�)�.�This���is���the�)time-consuming�)part�of�this�initialisation�metho�Gd.�The�user�can�o���v�erwrite�)the�function��PGFingerprint�.����b)��TCharacteristic�Subgroups����Compute��a�generating��set�for�the�stabiliser�in��GL�(�d���;����p����)�of�a�c���hain�of�c�haracteristic�subgroups��of��G��I�.�In���practice,��tw���e��uconstruct�a�c���haracteristic�c�hain��ub�y�determining��u2-step�cen�tralisers��uand�omega�subgroups�of���factors�UUof�the�lo���w�er�UU�p����-cen�tral�series.���Ho���w�ev�er,�E4there�E3are�often�other�c���haracteristic�subgroups�whic�h�E3are�not�found�b���y�these�approac�hes.�E3The�user���can�UUo���v�erwrite�the�function��PGCharSubgroups(�?�G�)��to�supply�a�set�of�c���haracteristic�subgroups.����c)��TDefaults������In��Jthe��Kmetho�Gd�for��AutomorphismGroup��w���e�use�a�default�strategy:�if�the�v��q�alue����������~�@p��q���r�A�':
cmti10�Ad����O!�cmsy7��1���~�);�fe��������>�@p�q��1�����~�is�less�than�1000,�then���w���e���use���the�minimal�o���v�ergroup���approac�h,�otherwise���the�c�haracteristic�subgroups���are�emplo�y�ed.���An�exception���is�UUmade�for�homogeneous�ab�Gelian�groups�where�w���e�initialise�the�algorithm�with�the�full�group��GL�(�d���;����p����).�����4.3��`Stabilisers�n�in�matrix�groups��N8��Consider��qthe��i�ګth�inductiv���e�step�of�the�algorithm.�Here��A�����A���ut��ث(�G����@i��\$�)��qacts�as�matrix�group�on�the�elemen�tary���ab�Gelian�UU�p����-group��M���and�w���e�w�an�t�to�determine�the�stabiliser�of�a�subgroup��U�j�����M����.���W��*�e�}use�the�}MeatAxe�to�compute�a�series�of��A�-in���v��q�arian�t�}subspaces�through��M� ��suc���h�that�eac���h�factor�in�the���series�=is�irreducible�<as��A�-mo�Gdule.�Then�w���e�use�this�series�to�break�the�computation�of��Stab����@A����(�U����)�in���to�sev�eral���smaller�UUorbit-stabiliser�calculations.���Note�6�that�6�a�theoretic�argumen���t�yields�an��A�-in���v��q�arian�t�subspace�6�of��M��u�a�priori:�the�n���ucleus��N����.�This�is�alw���a�ys���used�gto�hsplit�the�computation�up.�Ho���w�ev�er,�git�ma�y�ghapp�Gen�that��N�j��=���M�"��and�hence�results�in�no�impro���v�emen�t.��������1������L�I���CHOP���E�ff&f��ǫMULT���l�V��N8�The���in���v��q�arian�t�series�through��M�gd�is�computed�and�used�if�the�global�v��q�ariable��CHOP���E�ff&f��ǫMULT��x�is�set�to��true�.���Otherwise,�UUthe�algorithm�tries�to�determine��Stab����@A����(�U����)�in�one�step.�By�default,��CHOP���E�ff&f��ǫMULT��is��true�.�����
I+�����10�)���Chapter���4.�In
uencing�the�algorithm���p������4.4��`Sea��lrching�n�fo�r�a�small�generating�set��N8��After��eac���h�step��of�the�computation,�w�e�attempt�to��nd�a�nice�generating�set�for�the�automorphism�group���of�UUthe�curren���t�factor.��N8�If��the��automorphism�group�is�soluble,�w���e�store�a�p�Golycyclic�generating�set;�otherwise,�w���e�store�suc���h�a���generating���set�for���a�large�soluble�normal�subgroup��S��F�of�the�automorphism�group��A�,�and�as�few�generators���outside�� as�p�Gossible.��!If��S���=�hi�A��and�a�p�Golycyclic�generating�set�for��S�蝫is�kno���wn,�man�y�steps��!of�the�algorithm���pro�Gceed�UUmore�rapidly��*�.��������1������L�I���NICE���E�ff&f��ǫSTAB���l�V��N8�It���ma���y�b�Ge�b�oth�time-consuming�and�dicult�to�reduce�the���n���um�b�er���of�generators�for��A��outside��S�2}�.�Note�that�if���the�M#initialisation�of�the�algorithm�is�b���y��InitAutomorphismGroupOver�,�then�w�e�alw�a�ys�kno�w�a�p�Germ�utation���represen���tation���for����A�=�S�2}�.�Occasionally�the�searc���h�for�a�small�generating�set�is�exp�Gensiv���e.�If�this�is�observ���ed,���one�UUcould�set�the�
ag��NICE���E�ff&f��ǫSTAB��to��false��and�the�algorithm�no�longer�in���v�ok�es�UUthis�searc���h.��N8��4.5��`An�n�interactive�version�of�the�algo��lrithm����The��c���hoice�of��initialisation�and�the�c�hoice��of�c�hopping�of�the���p����-m�ultiplicator�can�also�b�Ge��driv�en�b�y�an���in���teractiv�e�UUv�ersion�of�the�algorithm.�W��*�e�giv�e�an�example.����9��gap>�?�G�:=�SmallGroup(�2^8,�1000�);;����9�gap>�?�SetInfoLevel(�InfoAutGrp,�3�);����9�gap>�?�AutomorphismGroupPGroup(�G,�true�);����9�#I�
�step�?�1:�2^3�--�init�automorphisms����9�choose�?�initialisation�(Over/Char/Full):�?�#�we�choose�Full����9�#I���init�?�automorphism�group�:�Full����9�#I�
�step�?�2:�2^3�--�aut�grp�has�size�168����9�#I���computing�?�cover����9�#I���computing�?�matrix�action����9�#I���computing�?�stabilizer�of�U����9�#I���dim�?�U�=�3�
�dim�N�=�6�dim�M�=�6����9�chop�?�M/N�and�N:�(y/n):�s�#�we�choose�n����9�#I���induce�?�autos�and�add�central�autos����9�#I�
�step�?�3:�2^2�--�aut�grp�has�size�12288����9�#I���computing�?�cover����9�#I���computing�?�matrix�action����9�#I���computing�?�stabilizer�of�U����9�#I���dim�?�U�=�6�
�dim�N�=�5�dim�M�=�8����9�chop�?�M/N�and�N:�(y/n):�s�#�we�choose�y����9�#I���induce�?�autos�and�add�central�autos����9�#I�
�final�?�step:�convert����9�rec(������glAutos�?�:=�[�Pcgs([�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->�[�f1,�f2*f3,�f3,����B��f4,�?�f5,�f6*f7,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1*f3*f5*f6,�f2*f3,�f3,�f4,�f5*f8,�f6*f7,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1*f3,�f2*f4,�f3,�f4*f7,�f5*f7,�f6*f7*f8,�f7,�f8�]�],�glOrder�:=�4,�����X:�����Se��}'ction���6.�A�cknow���le�dgements�Jt٫11���p���������agAutos�?�:=����#9�[�?�Pcgs([�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->�[�f1*f4,�f2,�f3,�f4*f8,�f5,����B��f6,�?�f7,�f8�],�Pcgs([�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2*f4,�f3,�f4*f7,�f5,�f6*f7*f8,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1*f5,�f2,�f3,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2*f5,�f3,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2,�f3*f5,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1*f6,�f2,�f3,�f4,�f5*f7*f8,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2*f6,�f3,�f4*f7*f8,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1*f8,�f2,�f3,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2*f8,�f3,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2,�f3*f8,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1*f7,�f2,�f3,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2*f7,�f3,�f4,�f5,�f6,�f7,�f8�],����-��Pcgs([�?�f1,�f2,�f3,�f4,�f5,�f6,�f7,�f8�])�->����89�[�?�f1,�f2,�f3*f7,�f4,�f5,�f6,�f7,�f8�]�],������agOrder�?�:=�[�2,�2,�2,�2,�2,�2,�2,�2,�2,�2,�2,�2,�2�],������one�?�:=�IdentityMapping(�<pc�group�of�size�256�with�8�generators>�),������group�?�:=�<pc�group�of�size�256�with�8�generators>,�size�:=�32768�)��N8��Tw���o��p�Goin�ts��are�w�orth�y��of�commen�t.�First,��the�in�teractiv�e��v�ersion�of��the�algorithm�p�Germits�the�user�to�mak���e���a�:suitable�:c���hoice�in�eac���h�step�of�the�algorithm�instead�of�making�one�c���hoice�at�the�b�Geginning.�Secondly��*�,�the���output�Q�of�Q�the��Info��function�sho���ws�the�ranks�of�the��p����-m���ultiplicator�and�allo���w�able�subgroup,�Q�and�th�us�Q�allo�w���the�UUuser�to�observ���e�the�scale�of�dicult�y�of�the�computation.��N8��4.6��`Ackno��lwledgements����W��*�e���thank�Alexander�Hulpk���e���for�helping�us�with�eciency�problems.�W�erner���Nic���k�el���pro�vided�some�functions���from�UUthe��GAP��PQuotient��whic���h�are�used�in�this�pac�k��q�age.�����c����p����E����j)�5���������Additional�
޽F����eatures��,���A]of��&the��'P����ack�age����:ꪍ�As�;�an�additional�;�feature�of�this�pac���k��q�age�w�e�;�pro�vide�some�functions�;�to�coun�t�extensions�of�;��p����-groups�and�Lie���algebras�UUo���v�er��GF�T��(�p����).�These�functions�ha�v�e�b�Geen�used�in�coun�ting�the�2-groups�of�size�2���^��10��x�.��������1������L�I���NumberOfPClass2PGroups(�?�n,�p,�k�)��N8��determines�UUthe�n���um�b�Ger�UUof��n��c�-generator��p����-groups�of��p��-class�2�with�F��*�rattini�subgroup�of�order�2���^��@k��y3�.��������2������L�I���NumberOfPClass2PGroups(�?�n,�p�)����returns�Ua�list�of�Uof�n���um�b�Gers�Uof��n��c�-generator��p����-groups�of��p����-class�2�with�F��*�rattini�subgroup�of�order�2���^��@k���8�for��k�h��in���1�;����:�:�:����;����n��c�(�n��C�+�8�1)�=�2.��������3������L�I���NumberOfClass2LieAlgebras(�?�n,�p,�k�)����determines�&the�'n���um�b�Ger�of�'�n��c�-generator�Lie�algebras�of�class�2�o���v�er�'�GF�T��(�p����)�with�deriv���ed�Lie�subalgebra�of���dimension�UU�k���.��������4������L�I���NumberOfClass2LieAlgbras(�?�n,�p�)����returns��a��list�of�of�n���um�b�Gers��of��n��c�-generator�Lie�algebras�of�class�2�o���v�er���GF�T��(�p����)�with�deriv���ed�Lie�subalgebra���of�UUdimension��k�h�for��k��in�1�;����:�:�:����;����n��c�(�n��C��8�1)�=�2.�����
m5�����p���������@U�Index����8N8��This�3�index�3�co���v�ers�only�this�3�man�ual.�A�3tpage�n�um�b�Ger�3�in��italics��refers�to�a�whole�section�whic���h�is�dev���oted���to���the�indexed�sub��8ject.�Keyw���ords�are�sorted�with�case�and�spaces�ignored,�e.g.,�\�PermutationCharacter�"���comes�UUb�Gefore�\p�erm���utation�group".���*����������^��A����Ac���kno�wledgemen�ts,�UU�11����An�UUin���teractiv�e�v�ersion�of�the�algorithm,��10����AutomorphismGroup�,�UU4����AutomorphismGroupPGroup�,�UU6����C����CHOP���E�ff&f��ǫMULT�,�UU9����ConvertHybridAutGroup�,�UU6����I����InfoAutGrp�,�UU4����N����NICE���E�ff&f��ǫSTAB�,�UU10����NumberOfClass2LieAlgbras�,�UU12������������d����NumberOfClass2LieAlgebras�,�UU12������NumberOfPClass2PGroups�,�UU12������O������Outline�UUof�the�algorithm,��8������P������PcGroupAutPGroup�,�UU7������S������Searc���hing�UUfor�a�small�generating�set,��10������SetInfoLevel�,�UU4�����Stabilisers�UUin�matrix�groups,��9������T������The�UUinitialisation�step,��9���������r����;���
�A�':
cmti10�@�':
cmti10�>p��i
cmssdc10�<p��i(
cmssdc10�;�>a�h�h�cminch�3�u�7msam7�$�':

cmti10���<x

cmtt10��"V

cmbx10�m#�R

cmss10�O!�cmsy7�!",�

cmsy10��b>

cmmi10�ٓ�Rcmr7�|{Ycmr8�K�`y

cmr10�wX����