GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
����; � 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�died�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�renemen���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).�� ������|{Y cmr8�1������L�3�u�7 msam7�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�UUelds:����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�dened�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-dened�c�hoices.�The��p�Gossible�v��q�alues�for�� ag��8�are��N8�� ag�"z�=�?�false����$ �the�UUuser-dened�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>