#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Alexander Hulpke.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains routines that are primarily of interest in a teaching
## context. It is made part of the general system to ensure it will be
## always installed with GAP.
##
#############################################################################
##
#F RankQGroup( <G> )
##
## <#GAPDoc Label="RankQGroup">
## <ManSection>
## <Func Name="RankQGroup" Arg='G'/>
##
## <Description>
## For a <M>p</M>-group <A>G</A> (see <Ref Func="IsQGroup"/>),
## <Ref Func="RankQGroup"/> returns the <E>rank</E> of <A>G</A>,
## which is defined as the minimal size of a generating system of <A>G</A>.
## If <A>G</A> is not a <M>p</M>-group then an error is issued.
## <Example><![CDATA[
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
#############################################################################
##
#F ListOfDigits( <G> )
##
## <#GAPDoc Label="ListOfDigits">
## <ManSection>
## <Func Name="ListOfDigits" Arg='n'/>
##
## <Description>
## For a positive integer <A>n</A> this function returns a list <A>l</A>,
## consisting of the digits of <A>n</A> in decimal representation.
## <Example><![CDATA[
## gap> ListOfDigits(3142);
## [ 3, 1, 4, 2 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("ListOfDigits");
#############################################################################
##
#F RootsOfPolynomial( <p> )
##
## <#GAPDoc Label="RootsOfPolynomial">
## <ManSection>
## <Func Name="RootsOfPolynomial" Arg='[R,],p'/>
##
## <Description>
## For a univariate polynomial <A>p</A>, this function returns all roots of
## <A>p</A> over the ring <A>R</A>. If the ring is not specified, it defaults
## to the ring specified by the coefficients of <A>p</A> via
## <Ref Func="DefaultRing" Label="for ring elements"/>).
## <Example><![CDATA[
## gap> x:=X(Rationals,"x");;p:=x^4-1;
## x^4-1
## gap> RootsOfPolynomial(p);
## [ 1, -1 ]
## gap> RootsOfPolynomial(CF(4),p);
## [ 1, -1, E(4), -E(4) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("RootsOfPolynomial");
#############################################################################
##
#F ShowGcd( <a>,<b> )
##
## <#GAPDoc Label="ShowGcd">
## <ManSection>
## <Func Name="ShowGcd" Arg='a,b'/>
##
## <Description>
## This function takes two elements <A>a</A> and <A>b</A> of an Euclidean
## ring and returns their
## greatest common divisor. It will print out the steps performed by the
## Euclidean algorithm, as well as the rearrangement of these steps to
## express the gcd as a ring combination of <A>a</A> and <A>b</A>.
## <Example><![CDATA[
## gap> ShowGcd(192,42);
## 192=4*42 + 24
## 42=1*24 + 18
## 24=1*18 + 6
## 18=3*6 + 0
## The Gcd is 6
## = 1*24 -1*18
## = -1*42 + 2*24
## = 2*192 -9*42
## 6
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("ShowGcd");
#############################################################################
##
#F ShowAdditionTable( <R> )
#F ShowMultiplicationTable( <M> )
##
## <#GAPDoc Label="ShowAdditionTable">
## <ManSection>
## <Func Name="ShowAdditionTable" Arg='R'/>
## <Func Name="ShowMultiplicationTable" Arg='M'/>
##
## <Description>
## For a structure <A>R</A> with an addition given by <C>+</C>,
## respectively a structure <A>M</A> with a multiplication given by <C>*</C>,
## this command displays the addition (multiplication) table of the structure
## in a pretty way.
## <Example><![CDATA[
## gap> ShowAdditionTable(GF(4));
## + | 0*Z(2) Z(2)^0 Z(2^2) Z(2^2)^2
## ---------+------------------------------------
## 0*Z(2) | 0*Z(2) Z(2)^0 Z(2^2) Z(2^2)^2
## Z(2)^0 | Z(2)^0 0*Z(2) Z(2^2)^2 Z(2^2)
## Z(2^2) | Z(2^2) Z(2^2)^2 0*Z(2) Z(2)^0
## Z(2^2)^2 | Z(2^2)^2 Z(2^2) Z(2)^0 0*Z(2)
##
##gap> ShowMultiplicationTable(GF(4));
##* | 0*Z(2) Z(2)^0 Z(2^2) Z(2^2)^2
##---------+------------------------------------
##0*Z(2) | 0*Z(2) 0*Z(2) 0*Z(2) 0*Z(2)
##Z(2)^0 | 0*Z(2) Z(2)^0 Z(2^2) Z(2^2)^2
##Z(2^2) | 0*Z(2) Z(2^2) Z(2^2)^2 Z(2)^0
##Z(2^2)^2 | 0*Z(2) Z(2^2)^2 Z(2)^0 Z(2^2)
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("ShowMultiplicationTable");
DeclareGlobalFunction("ShowAdditionTable");
#############################################################################
##
#F CosetDecomposition( <G> )
##
## <#GAPDoc Label="CosetDecomposition">
## <ManSection>
## <Func Name="CosetDecomposition" Arg='G,S'/>
##
## <Description>
## For a finite group <A>G</A> and a subgroup <M><A>S</A> \leq <A>G</A></M>
## this function returns a partition of the elements of <A>G</A> according to
## the (right) cosets of <A>S</A>. The result is a list of lists, each sublist
## corresponding to one coset. The first sublist is the elements list of the
## subgroup, the other lists are arranged accordingly.
## <Example><![CDATA[
## gap> CosetDecomposition(SymmetricGroup(4),SymmetricGroup(3));
## [ [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ],
## [ (1,4), (1,4)(2,3), (1,2,4), (1,2,3,4), (1,3,2,4), (1,3,4) ],
## [ (1,4,2), (1,4,2,3), (2,4), (2,3,4), (1,3)(2,4), (1,3,4,2) ],
## [ (1,4,3), (1,4,3,2), (1,2,4,3), (1,2)(3,4), (2,4,3), (3,4) ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("CosetDecomposition");
#############################################################################
##
#F AllHomomorphismClasses( <G>,<H> )
##
## <#GAPDoc Label="AllHomomorphismClasses">
## <ManSection>
## <Func Name="AllHomomorphismClasses" Arg='G,H'/>
##
## <Description>
## For two finite groups <A>G</A> and <A>H</A>, this function returns
## representatives of all homomorphisms <M><A>G</A> to <A>H</A></M> up to
## <A>H</A>-conjugacy.
## <Example><![CDATA[
## gap> AllHomomorphismClasses(SymmetricGroup(4),SymmetricGroup(3));
## [ [ (2,4,3), (1,4,2,3) ] -> [ (), () ],
## [ (2,4,3), (1,4,2,3) ] -> [ (), (1,2) ],
## [ (2,4,3), (1,4,2,3) ] -> [ (1,2,3), (1,2) ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("AllHomomorphismClasses");
#############################################################################
##
#F AllHomomorphisms( <G>,<H> )
##
## <#GAPDoc Label="AllHomomorphisms">
## <ManSection>
## <Func Name="AllHomomorphisms" Arg='G,H'/>
## <Func Name="AllEndomorphisms" Arg='G'/>
## <Func Name="AllAutomorphisms" Arg='G'/>
##
## <Description>
## For two finite groups <A>G</A> and <A>H</A>, this function returns
## all homomorphisms <M><A>G</A> to <A>H</A></M>. Since this number will
## grow quickly, <Ref Func="AllHomomorphismClasses"/> should be used in most
## cases.
## <Ref Func="AllEndomorphisms"/> returns all homomorphisms from
## <A>G</A> to itself,
## <Ref Func="AllAutomorphisms"/> returns all bijective endomorphisms.
## <Example><![CDATA[
## gap> AllHomomorphisms(SymmetricGroup(3),SymmetricGroup(3));
## [ [ (2,3), (1,2,3) ] -> [ (), () ],
## [ (2,3), (1,2,3) ] -> [ (1,2), () ],
## [ (2,3), (1,2,3) ] -> [ (2,3), () ],
## [ (2,3), (1,2,3) ] -> [ (1,3), () ],
## [ (2,3), (1,2,3) ] -> [ (2,3), (1,2,3) ],
## [ (2,3), (1,2,3) ] -> [ (1,3), (1,2,3) ],
## [ (2,3), (1,2,3) ] -> [ (1,3), (1,3,2) ],
## [ (2,3), (1,2,3) ] -> [ (1,2), (1,2,3) ],
## [ (2,3), (1,2,3) ] -> [ (2,3), (1,3,2) ],
## [ (2,3), (1,2,3) ] -> [ (1,2), (1,3,2) ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("AllHomomorphisms");
#############################################################################
##
#F AllSubgroups( <G> )
##
## <#GAPDoc Label="AllSubgroups">
## <ManSection>
## <Func Name="AllSubgroups" Arg='G'/>
##
## <Description>
## For a finite group <A>G</A>
## <Ref Func="AllSubgroups"/> returns a list of all subgroups of <A>G</A>,
## intended primarily for use in class for small examples.
## This list will quickly get very long and in general use of
## <Ref Attr="ConjugacyClassesSubgroups"/> is recommended.
## <Example><![CDATA[
## gap> AllSubgroups(SymmetricGroup(3));
## [ Group(()), Group([ (2,3) ]), Group([ (1,2) ]), Group([ (1,3) ]),
## Group([ (1,2,3) ]), Group([ (1,2,3), (2,3) ]) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BindGlobal("AllSubgroups",
function(G)
local cl;
cl:=ConjugacyClassesSubgroups(G);
if Sum(cl,Size)>10^5 then
Info(InfoPerformance,1,"G has ",Sum(cl,Size),
" subgroups. Writing them all down\n",
"takes lots of memory and time. Use `ConjugacyClassesSubgroups' to get\n",
"classes up to conjugaction action, this will be more efficient!");
fi;
return Concatenation(List(cl,AsSSortedList));
end);
#############################################################################
##
#F CheckDigitTestFunction( <l>,<m>,<f> )
##
## <#GAPDoc Label="CheckDigitTestFunction">
## <ManSection>
## <Func Name="CheckDigitTestFunction" Arg='l,m,f'/>
##
## <Description>
## This function creates check digit test functions such as
## <Ref Func="CheckDigitISBN"/> for check digit schemes that use the inner
## products with a fixed vector modulo a number. The scheme creates will use
## strings of <A>l</A> digits (including the check digits), the check consists
## of taking the standard product of the vector of digits with the fixed vector
## <A>f</A> modulo <A>m</A>; the result needs to be 0.
##
## The function returns a function that then can be used for testing or
## determining check digits.
## <Example><![CDATA[
## gap> isbntest:=CheckDigitTestFunction(10,11,[1,2,3,4,5,6,7,8,9,-1]);
## function( arg... ) ... end
## gap> isbntest("038794680");
## Check Digit is 2
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("CheckDigitTestFunction");
#############################################################################
##
#F CheckDigitISBN( <n> )
##
## <#GAPDoc Label="CheckDigitISBN">
## <ManSection>
## <Func Name="CheckDigitISBN" Arg='n'/>
## <Func Name="CheckDigitISBN13" Arg='n'/>
## <Func Name="CheckDigitPostalMoneyOrder" Arg='n'/>
## <Func Name="CheckDigitUPC" Arg='n'/>
##
## <Description>
## These functions can be used to compute, or check, check digits for some
## everyday items. In each case what is submitted as input is either the number
## with check digit (in which case the function returns <K>true</K> or
## <K>false</K>), or the number without check digit (in which case the function
## returns the missing check digit). The number can be specified as integer, as
## string (for example in case of leading zeros) or as a sequence of arguments,
## each representing a single digit.
##
## The check digits tested are the 10-digit ISBN (International Standard Book
## Number) using <Ref Func="CheckDigitISBN"/> (since arithmetic is module 11, a
## digit 11 is represented by an X);
## the newer 13-digit ISBN-13 using <Ref Func="CheckDigitISBN13"/>;
## the numbers of 11-digit US postal money orders using
## <Ref Func="CheckDigitPostalMoneyOrder"/>; and
## the 12-digit UPC bar code found on groceries using
## <Ref Func="CheckDigitUPC"/>.
## <Example><![CDATA[
## gap> CheckDigitISBN("052166103");
## Check Digit is 'X'
## 'X'
## gap> CheckDigitISBN("052166103X");
## Checksum test satisfied
## true
## gap> CheckDigitISBN(0,5,2,1,6,6,1,0,3,1);
## Checksum test failed
## false
## gap> CheckDigitISBN(0,5,2,1,6,6,1,0,3,'X'); # note single quotes!
## Checksum test satisfied
## true
## gap> CheckDigitISBN13("9781420094527");
## Checksum test satisfied
## true
## gap> CheckDigitUPC("07164183001");
## Check Digit is 1
## 1
## gap> CheckDigitPostalMoneyOrder(16786457155);
## Checksum test satisfied
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
#############################################################################
##
#F NumbersString( <S>,<m>[,<table>] )
##
## <#GAPDoc Label="NumbersString">
## <ManSection>
## <Func Name="NumbersString" Arg='s,m [,table]'/>
##
## <Description>
## <Ref Func="NumbersString"/> takes a string message <A>s</A> and
## returns a list of integers, each not exceeding the integer <A>m</A>
## that encode the
## message using the scheme <M>A=11</M>, <M>B=12</M> and so on (and
## converting lower case to upper case).
## If a list of characters is given in <A>table</A>,
## it is used instead for encoding).
## <Example><![CDATA[
## gap> l:=NumbersString("Twas brillig and the slithy toves",1000000);
## [ 303311, 291012, 281922, 221917, 101124, 141030, 181510, 292219,
## 301835, 103025, 321529 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("NumbersString");
#############################################################################
##
#F StringNumbers( <l>,<m>[,<table>] )
##
## <#GAPDoc Label="StringNumbers">
## <ManSection>
## <Func Name="StringNumbers" Arg='l,m [,table]'/>
##
## <Description>
## <Ref Func="StringNumbers"/> takes a list <A>l</A> of integers that was
## encoded using <Ref Func="NumbersString"/> and the size integer <A>m</A>,
## and returns a
## message string, using the scheme <M>A=11</M>, <M>B=12</M> and so on.
## If a list of characters is given in <A>table</A>,
## it is used instead for decoding).
## <Example><![CDATA[
## gap> StringNumbers(l,1000000);
## "TWAS BRILLIG AND THE SLITHY TOVES"
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("StringNumbers");
#############################################################################
##
#F SetNameObject( <o>,<s> )
##
## <#GAPDoc Label="SetNameObject">
## <ManSection>
## <Func Name="SetNameObject" Arg='o,s'/>
##
## <Description>
## <Ref Func="SetNameObject"/>
## sets the string <A>s</A> as display name for object <A>o</A> in an
## interactive session. When applying <Ref Func="View"/> to
## object <A>o</A>, for example in the system's main loop,
## &GAP; will print the string <A>s</A>.
## Calling <Ref Func="SetNameObject"/> for the same object <A>o</A> with
## <A>s</A> set to <Ref Var="fail"/>
## deletes the special viewing setup.
## Since use of this features potentially slows down the whole print
## process, this function should be used sparingly.
## <Example><![CDATA[
## gap> SetNameObject(3,"three");
## gap> Filtered([1..10],IsPrimeInt);
## [ 2, three, 5, 7 ]
## gap> SetNameObject(3,fail);
## gap> Filtered([1..10],IsPrimeInt);
## [ 2, 3, 5, 7 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("SetNameObject");
## SetExecutionObject(<o>,<f>) sets a ``view execution'' for object <o>.
## When viewing <o>, function <f> will be called on <o>. This can be used
## to have elements display their action as symmetries of an object.
## SetExecutionObject(<o>,fail);
## deletes the special viewing setup.
DeclareGlobalFunction("SetExecutionObject");
InstallGlobalFunction(CosetDecomposition,function(G,S)
local i,l,e;
e:=AsSSortedList(S);
l:=[e];
for i in RightTransversal(G,S) do
if not i in S then
Add(l,List(e,x->x*i));
fi;
od;
return l;
end);
BindGlobal("StringLC",function(x,a,y,b)
local s;
x:=String(x);
if '+' in x or '-' in x then
if x[1]<>'-' or '+' in x{[2..Length(x)]} or '-' in x{[2..Length(x)]} then
x:=Concatenation("(",x,")");
fi;
fi;
a:=String(a);
if '+' in a or '-' in a then
a:=Concatenation("(",String(a),")");
fi;
s:=Concatenation(x,"*",a);
if IsOne(y) then
s:=Concatenation(s," + ",String(b));
return s;
fi;
y:=String(y);
if '+' in y or '-' in y then
if y[1]<>'-' or '+' in y{[2..Length(y)]} or '-' in y{[2..Length(y)]} then
y:=Concatenation("(",y,")");
fi;
fi;
if y[1]<>'-' then
s:=Concatenation(s," + ");
else
s:=Concatenation(s," ");
fi;
b:=String(b);
if '+' in b or '-' in b then
b:=Concatenation("(",String(b),")");
fi;
s:=Concatenation(s,y,"*",b);
return s;
end);
InstallGlobalFunction(ShowGcd,function(a,b)
local qrs, qr, oa, g, c, d, nd;
qrs:=[];
while not IsZero(b) do
qr:=QuotientRemainder(a,b);
if not IsZero(qr[1]) then
Add(qrs,qr); # avoid a first flipping step
fi;
Print(a,"=",StringLC(qr[1],b,1,qr[2]),"\n");
oa:=a;
a:=b;
b:=qr[2];
od;
Print("The Gcd is ",a,"\n");
g:=a;
qrs:=Reversed(qrs{[1..Length(qrs)-1]});
a:=oa;
c:=0;
d:=1;
for qr in qrs do
b:=a;
a:=qr[1]*b+qr[2];
nd:=c-d*qr[1];
c:=d;
d:=nd;
Print(" = ",StringLC(c,a,d,b),"\n");
od;
return g;
end);
InstallGlobalFunction(RootsOfPolynomial,function(arg)
local p, R;
p:=Last(arg);
if not IsUnivariatePolynomial(p) then
Error("<p> must be an univariate polynomial");
fi;
if IsRationalFunctionsFamilyElement(p) then # UFD
if Length(arg)>1 then
return RootsOfUPol(arg[1],p);
else
return RootsOfUPol(p);
fi;
else
if Length(arg)>1 then
R:=arg[1];
else
R:=DefaultRing(CoefficientsOfUnivariatePolynomial(p));
fi;
if Size(R)>10^7 then
Error("R is not an UFD and too large to test for roots");
fi;
return Filtered(Enumerator(R),x->IsZero(Value(p,x)));
fi;
end);
InstallGlobalFunction(ListOfDigits,function(arg)
local a, l, b, i;
if Length(arg)=1 and IsString(arg[1]) then
l:=ShallowCopy(arg[1]);
l:=Filtered(l,i->not i in "([-)]");
for i in [1..Length(l)] do
if l[i] in CHARS_DIGITS then
l[i]:=Position(CHARS_DIGITS,l[i])-1;
fi;
od;
elif Length(arg)=1 and IsInt(arg[1]) then
a:=AbsInt(arg[1]);
l:=[];
while a<>0 do
b:=a mod 10;
Add(l,b);
a:=(a-b)/10;
od;
l:=Reversed(l);
elif Length(arg)=1 and IsList(arg[1])
and ForAll(arg[1],i->(IsInt(i) and 0<=i and 9>=i)
or (i in CHARS_UALPHA)) then
l:=ShallowCopy(arg[1]);
elif IsList(arg) and ForAll(arg,i->(IsInt(i) and 0<=i and 9>=i)
or (i in CHARS_UALPHA)) then
l:=ShallowCopy(arg);
else
Error("Number must be given as integer, as string or as list of digits");
fi;
return l;
end);
InstallGlobalFunction(CheckDigitTestFunction,function(len,modulo,scalars)
return function(arg)
local l, s, i;
l:=CallFuncList(ListOfDigits,arg);
if Length(l)=len or Length(l)=len-1 then
s:=0;
for i in [1..len-1] do
s:=s+scalars[i]*l[i] mod modulo;
od;
s:=s/(-scalars[len]) mod modulo;
if s=10 then
s:='X';
fi;
if Length(l)=len then
if s=l[len] then
Print("Checksum test satisfied\n");
else
Print("Checksum test failed\n");
fi;
return s=l[len];
else # length=l-1
Print("Check Digit is ",s,"\n");
return s;
fi;
fi;
Error("number is of wrong length");
end;
end);
BindGlobal("CheckDigitISBN",
CheckDigitTestFunction(10,11,[1,2,3,4,5,6,7,8,9,-1]));
BindGlobal("CheckDigitISBN13",
CheckDigitTestFunction(13,10,[1,3,1,3,1,3,1,3,1,3,1,3,1]));
BindGlobal("CheckDigitPostalMoneyOrder",
CheckDigitTestFunction(11,9,[1,1,1,1,1,1,1,1,1,1,-1]));
BindGlobal("CheckDigitUPC",
CheckDigitTestFunction(12,10,[3,1,3,1,3,1,3,1,3,1,3,1]));
# print tables
BindGlobal("DoPrintTable",function(elm,opstring,operation)
local l,str,m,i,j,p;
str:=[];
elm:=ShallowCopy(elm);
l:=Length(elm);
for i in [1..l] do
p:=String(elm[i]);
Add(str,p);
od;
# test closure
for i in [1..l] do
for j in [1..l] do
p:=operation(elm[i],elm[j]);
if not p in elm then
Add(elm,p);
Add(str,String(p));
fi;
od;
od;
for i in [1..Length(str)] do
p:=str[i];
# shorten
p:=ReplacedString(p,"ZmodnZObj","ZnZ");
p:=ReplacedString(p,"ZmodpZObj","ZnZ");
p:=ReplacedString(p,"identity ...","id");
str[i]:=p;
od;
# test closure, if necessary add further elements
m:=Maximum(List(str,Length));
m:=Maximum(m,Length(opstring));
while Length(opstring)<m do
opstring:=Concatenation(opstring," ");
od;
for i in [1..Length(str)] do
while Length(str[i])<m do
str[i]:=Concatenation(str[i]," ");
od;
od;
Print(opstring," |\c");
for i in [1..l] do
Print(" ",str[i],"\c");
od;
p:=ListWithIdenticalEntries((Length(elm)+1)*(m+1)+1,'-');
p[m+2]:='+';
Print("\n",p,"\n");
for i in [1..l] do
Print(str[i]," |\c");
for j in [1..l] do
p:=Position(elm,operation(elm[i],elm[j]));
p:=str[p];
Print(" ",p,"\c");
od;
Print("\n");
od;
Print("\n");
end);
InstallGlobalFunction(ShowMultiplicationTable,function(arg)
local obj,op;
obj:=arg[1];
if not IsList(obj) then
obj:=AsSSortedList(obj);
fi;
op:=\*;
if Length(arg)>1 and IsInt(arg[2]) then
op:=function(a,b) return a*b mod arg[2];end;
fi;
DoPrintTable(obj,"*",op);
end);
InstallGlobalFunction(ShowAdditionTable,function(arg)
local obj,op;
obj:=arg[1];
if not IsList(obj) then
obj:=AsSSortedList(obj);
fi;
op:=\+;
if Length(arg)>1 and IsInt(arg[2]) then
op:=function(a,b) return a+b mod arg[2];end;
fi;
DoPrintTable(obj,"+",op);
end);
#naming of objects
BindGlobal("SpecialViewSetupFunction",function(OBJLIST)
return function(o,n)
local p;
if not CanEasilyCompareElements(FamilyObj(o)) then
Error("Element is in family without efficient equality test.\n",
"This can cause problems");
fi;
p:=PositionProperty(OBJLIST,x->x[1]=o);
if p<>fail then
if n=fail then
# delete
Remove(OBJLIST, p);
else
OBJLIST[p][2]:=n;
fi;
elif n<>fail then
Add(OBJLIST,[o,n]);
fi;
end;
end);
if IsHPCGAP then
MakeThreadLocal("NAMEDOBJECTS");
MakeThreadLocal("EXECUTEOBJECTS");
BindThreadLocal("NAMEDOBJECTS", []);
BindThreadLocal("EXECUTEOBJECTS", []);
else
NAMEDOBJECTS:=[];
EXECUTEOBJECTS:=[];
fi;
InstallGlobalFunction(SetNameObject,SpecialViewSetupFunction(NAMEDOBJECTS));
InstallGlobalFunction(SetExecutionObject,
SpecialViewSetupFunction(EXECUTEOBJECTS));
# special view method for ``named'' objects or objects that should execute
# something.
InstallMethod(ViewObj,true,[IsObject],SUM_FLAGS,
function(o)
local i;
if Length(NAMEDOBJECTS)=0 and Length(EXECUTEOBJECTS)=0 then
TryNextMethod();
fi;
for i in EXECUTEOBJECTS do
if i[1]=o then
i[2](o); # EXECUTE
fi;
od;
for i in NAMEDOBJECTS do
if i[1]=o then
Print(i[2]);
return;
fi;
od;
TryNextMethod();
end);
# special string method for ``named'' objects.
InstallMethod(String,true,[IsObject],SUM_FLAGS,
function(o)
local i;
if Length(NAMEDOBJECTS)=0 then
TryNextMethod();
fi;
for i in NAMEDOBJECTS do
if i[1]=o then
return String(i[2]);
fi;
od;
TryNextMethod();
end);
# string/number list encoding
InstallGlobalFunction(NumbersString,function(arg)
local message,modulus,table,tenpow,bound,l,m,i,p;
message:=arg[1];
modulus:=arg[2];
if Length(arg)>2 then
table:=arg[3];
else
table:=Concatenation(ListWithIdenticalEntries(9,0)," ",
CHARS_UALPHA,CHARS_DIGITS,CHARS_SYMBOLS);
message:=UppercaseString(message);
fi;
if modulus<Length(table) then
Error("modulus must be at least as large as the translation table");
fi;
tenpow:=10^(LogInt(Length(table),10)+1);
bound:=Int(modulus/tenpow);
l:=[];
m:=0;
for i in message do
p:=Position(table,i);
if p=fail then
Error("Symbol ",i,"is not encodable");
fi;
if m<bound then
m:=m*tenpow+p;
else
Add(l,m);
m:=p;
fi;
od;
Add(l,m);
return l;
end);
InstallGlobalFunction(StringNumbers,function(arg)
local message,modulus,table,tenpow,l,i;
l:=arg[1];
modulus:=arg[2];
if Length(arg)>2 then
table:=arg[3];
else
table:=Concatenation(ListWithIdenticalEntries(9,0)," ",
CHARS_UALPHA,CHARS_DIGITS,CHARS_SYMBOLS);
fi;
if modulus<Length(table) then
Error("modulus must be at least as large as the translation table");
fi;
message:="";
tenpow:=10^(LogInt(Length(table),10)+1);
l:=Concatenation(List(l,x->Reversed(CoefficientsQadic(x,tenpow))));
for i in l do
if not IsBound(table[i]) then
Error("message uses illegal symbol ",i);
fi;
Add(message,table[i]);
od;
return message;
end);
# functions specific to Gallians textbook
BindGlobal("GallianUlist",function(n)
local o;
o:=One(Integers mod n);
return List(Filtered([1..n-1],i->Gcd(i,n)=1),i->i*o);
end);
BindGlobal("GallianCyclic",function(n,a)
if Gcd(a,n)<>1 then
Error("a must be coprime to n");
fi;
return AsSSortedList(Group(a*One(Integers mod n)));
end);
BindGlobal("GallianOrderFrequency",function(G)
local c,l,i,p;
c:=ConjugacyClasses(G);
l:=[];
for i in c do
p:=First(l,x->x[1]=Order(Representative(i)));
if p<>fail then
p[2]:=p[2]+Size(i);
else
AddSet(l,[Order(Representative(i)),Size(i)]);
fi;
od;
Print("[Order of element, Number of that order]=");
return l;
end);
BindGlobal("GallianCstruc",function(G,s)
local c,l,i;
c:=ConjugacyClasses(G);
l:=[];
for i in c do
if CycleStructurePerm(Representative(i))=s then
l:=Union(l,AsSSortedList(i));
fi;
od;
return l;
end);
# up to G-conjugacy
InstallGlobalFunction(AllHomomorphismClasses,function(H,G)
local cl,cnt,bg,bw,bo,bi,k,gens,go,imgs,params,emb,sg,c,i;
if not HasIsFinite(H) then
Info(InfoPerformance,1,"Forcing finiteness test -- might not terminate");
fi;
if not IsFinite(H) then
Error("the first argument must be a finite group");
fi;
if IsAbelian(G) and not IsAbelian(H) then
k:=NaturalHomomorphismByNormalSubgroup(H,DerivedSubgroup(H));
return List(AllHomomorphismClasses(Image(k),G),x->k*x);
fi;
cl:=ConjugacyClasses(G);
if IsCyclic(H) then
if Size(H)=1 then
k:=One(H);
else
k:=MinimalGeneratingSet(H)[1];
fi;
c:=Order(k);
Assert(1,Order(k)=Order(H));
cl:=List(cl,Representative);
cl:=Filtered(cl,x->IsInt(c/Order(x)));
return List(cl,x->GroupHomomorphismByImagesNC(H,G,[k],[x]));
fi;
# find a suitable generating system
bw:=infinity;
bo:=[0,0];
cnt:=0;
if IsFinite(H) then
repeat
if cnt=0 then
# first the small gen syst.
if IsSolvableGroup(H) and CanEasilyComputePcgs(H) then
gens:=MinimalGeneratingSet(H);
else
gens:=SmallGeneratingSet(H);
fi;
sg:=Length(gens);
else
# then something random
repeat
if Length(gens)>2 and Random(1,2)=1 then
# try to get down to 2 gens
gens:=List([1,2],i->Random(H));
else
gens:=List([1..sg],i->Random(H));
fi;
# try to get small orders
for k in [1..Length(gens)] do
go:=Order(gens[k]);
# try a p-element
if Random(1,3*Length(gens))=1 then
gens[k]:=gens[k]^(go/(Random(Factors(go))));
fi;
od;
until Index(H,SubgroupNC(H,gens))=1;
fi;
go:=List(gens,Order);
imgs:=List(go,i->Filtered(cl,j->IsInt(i/Order(Representative(j)))));
Info(InfoMorph,3,go,":",Product(imgs,i->Sum(i,Size)));
if Product(imgs,i->Sum(i,Size))<bw then
bg:=gens;
bo:=go;
bi:=imgs;
bw:=Product(imgs,i->Sum(i,Size));
elif Set(go)=Set(bo) then
# we hit the orders again -> sign that we can't be
# completely off track
cnt:=cnt+Int(bw/Size(G)*3);
fi;
cnt:=cnt+1;
until bw/Size(G)*3<cnt;
else
gens:=GeneratorsOfGroup(H);
bg:=gens;
imgs:=List(gens,x->cl);
bi:=imgs;
fi;
if bw=0 then
Error("trivial homomorphism not found");
fi;
# skipped verbal business
Info(InfoMorph,2,"find ",bw," from ",cnt);
if IsFinite(H) and Length(bg)>2 and cnt>Size(H)^2 and Size(G)<bw then
Info(InfoPerformance,1,
"The group tested requires many generators. `AllHomomorphismClasses' often\n",
"#I does not perform well for such groups -- see the documentation.");
fi;
params:=rec(gens:=bg,from:=H);
# find all homs
emb:=MorClassLoop(G,bi,params,
# all homs = 1+8
9);
Info(InfoMorph,2,Length(emb)," homomorphisms");
# skipped removal of duplicate images
return emb;
end);
InstallGlobalFunction(AllHomomorphisms,function(G,H)
local c,i,m,o,j;
c:=[];
for i in AllHomomorphismClasses(G,H) do
m:=MappingGeneratorsImages(i);
o:=Orbit(H,m[2],OnTuples);
for j in o do
Add(c,GroupHomomorphismByImages(G,H,m[1],j));
od;
od;
return c;
end);
BindGlobal("AllEndomorphisms",G->AllHomomorphisms(G,G));
BindGlobal("GallianHomoDn",AllEndomorphisms);
BindGlobal("AllAutomorphisms",G->AsSSortedList(AutomorphismGroup(G)));
BindGlobal("GallianAutoDn",AllAutomorphisms);
BindGlobal("GallianIntror2",n->RootsOfPolynomial(Indeterminate(Integers mod n)^2+1)
);
