From parth_dixit at da-iict.org Tue Jan 13 18:27:55 2004
From: parth_dixit at da-iict.org (parth dixit)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] subgroup of direct product
Message-ID: <200401131827.i0DIRtk22462@mail.da-iict.org>
hi,
I am trying to form a subgroup of Direct product of two groups by
taking direct product of subgroups of the original groups.But it is
giving me error,I tried using AsSubgroup too but it failed.Please help
me.
gap> G:=SymmetricGroup(5);;
gap> H1:=SymmetricGroup(3);;
gap> H2:=DihedralGroup(IsPermGroup,8);;
gap> gg:=DirectProduct(G,G);;
gap> hh:=DirectProduct(H1,H2);;
gap> IsSubgroup(gg,hh);
false
thanks
parth
From gap at gap.zssm.zp.ua Tue Jan 13 21:06:31 2004
From: gap at gap.zssm.zp.ua (Alexander Konovalov)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] subgroup of direct product
In-Reply-To: <200401131827.i0DIRtk22462@mail.da-iict.org>
References: <200401131827.i0DIRtk22462@mail.da-iict.org>
Message-ID: <1269532056.20040113230631@gap.zssm.zp.ua>
Dear Parth Dixit, dear GAP Forum
Let me suggest the following:
First the direct product
gap> g:=SymmetricGroup(5);
Sym( [ 1 .. 5 ] )
gap> dp:=DirectProduct(g,g);
Group([ (1,2,3,4,5), (1,2), (6,7,8,9,10), (6,7) ])
and embeddings into its components:
gap> f1:=Embedding(dp,1);
1st embedding into Group([ (1,2,3,4,5), (1,2), (6,7,8,9,10), (6,7) ])
gap> f2:=Embedding(dp,2);
2nd embedding into Group([ (1,2,3,4,5), (1,2), (6,7,8,9,10), (6,7) ])
Now your groups:
gap> h1:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> h2:=DihedralGroup(IsPermGroup,8);
Group([ (1,2,3,4), (2,4) ])
And their images under this embeddings (you see that these images are
subgroups of the direct product):
gap> k1:=Image(f1,h1);
Group([ (1,2,3), (1,2) ])
gap> IsSubgroup(dp,k1);
true
gap> k2:=Image(f2,h2);
Group([ (6,7,8,9), (7,9) ])
gap> IsSubgroup(dp,k2);
true
But even now their direct product can not be calculated as follows:
gap> s:=DirectProduct(k1,k2);
Group([ (1,2,3), (1,2), (4,5,6,7), (5,7) ])
gap> IsSubgroup(dp,s);
false
AND HERE IS THE CORRECT APPROACH:
gap> s:=ClosureGroup(k1,k2);
Group([ (2,3), (1,2,3), (6,7,8,9), (7,9) ])
gap> IsSubgroup(dp,s);
true
Hope this helps,
Sincerely yours,
Alexander Konovalov
On Tuesday, January 13, 2004 at 8:27:55 PM
parth dixit wrote:
> hi,
> I am trying to form a subgroup of Direct product of two groups by
> taking direct product of subgroups of the original groups.But it is
> giving me error,I tried using AsSubgroup too but it failed.Please help
> me.
gap>> G:=SymmetricGroup(5);;
gap>> H1:=SymmetricGroup(3);;
gap>> H2:=DihedralGroup(IsPermGroup,8);;
gap>> gg:=DirectProduct(G,G);;
gap>> hh:=DirectProduct(H1,H2);;
gap>> IsSubgroup(gg,hh);
> false
> thanks
> parth
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
From jjoao at netcabo.pt Thu Jan 22 18:33:59 2004
From: jjoao at netcabo.pt (Jose Joao Morais)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Semigroup homomorphism
Message-ID: <1074796444.4360.9.camel@localhost.localdomain>
Dear GAP Forum,
I am trying to define a semigroup homomorphism, so I looked at the code
for GroupGeneralMappingByImages in ghom.gi and tried to do something
similar for semigroups. This is what I did (poi5 is a semigroup of
transformations)
gap> G:=poi5;
gap> H:=G;
gap> filter:=HasSource and HasRange and HasMappingGeneratorsImages;
>">
gap> gens:=GeneratorsOfSemigroup(G);;
gap> imgs:=GeneratorsOfSemigroup(H);;
gap> mapi:=[Immutable(gens),Immutable(imgs)];;
gap> hom:=rec();
rec( )
gap> ObjectifyWithAttributes( hom,
> NewType( GeneralMappingsFamily
> ( ElementsFamily( FamilyObj( G ) ),
> ElementsFamily( FamilyObj( H ) ) ), filter ),
> Source,G,
> Range,H,
> MappingGeneratorsImages,mapi);
gap> SetIsMapping( hom, true );
gap> IsMapping(hom);
true
gap> Source(hom);
Error, no method found! For debugging hints type ?Recovery from
NoMethodFound
Error, no 1st choice method found for `Source' on 1 arguments called
from
( ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
I could not find the code for Source, so I would like to ask if
someone could tell me why this error happened or how can make this work.
Thank you
Jose Morais
From alexk at mcs.st-and.ac.uk Thu Jan 22 23:02:04 2004
From: alexk at mcs.st-and.ac.uk (alexk@mcs.st-and.ac.uk)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Hi
Message-ID:
Test =)
vurpwtmbdwhmps
--
Test, yep.
From jjoao at netcabo.pt Fri Jan 23 11:51:15 2004
From: jjoao at netcabo.pt (Jose Joao Morais)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Factorization for Semigroups
Message-ID: <1074858679.4359.21.camel@localhost.localdomain>
Dear GAP-Forum,
I need a Factorization function for semigroups (like the one for
groups) that given a semigroup and an element of this semigroup would
return the element's factorization in the generators of the semigroup.
I have looked at the code for 'Factorization' for groups but I could
not get any enlightenment, so my question is if anyone could give some
hints on how to implement such a function (what I do now is, starting
with the generators of the semigroup, perform all the multiplications
while storing the factors, but this takes too long for semigroups with
enough elements and becomes impracticable...).
Thank you very much,
Jose Morais
From andrew at illywhacker.net Fri Jan 23 22:04:11 2004
From: andrew at illywhacker.net (Andrew Solomon)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Factorization for Semigroups
In-Reply-To: <1074858679.4359.21.camel@localhost.localdomain>
References: <1074858679.4359.21.camel@localhost.localdomain>
Message-ID: <20040123220411.GA11283@it.uts.edu.au>
Dear Jose Morais
On Fri, Jan 23, 2004 at 11:51:19AM +0000, Jose Joao Morais wrote:
> Dear GAP-Forum,
>
> I need a Factorization function for semigroups (like the one for
> groups) that given a semigroup and an element of this semigroup would
> return the element's factorization in the generators of the semigroup.
>
> I have looked at the code for 'Factorization' for groups but I could
> not get any enlightenment, so my question is if anyone could give some
> hints on how to implement such a function (what I do now is, starting
> with the generators of the semigroup, perform all the multiplications
> while storing the factors, but this takes too long for semigroups with
> enough elements and becomes impracticable...).
>
According to Kozen
D. Kozen {\em Lower bounds for natural proof systems},
Proc. 18th Annual Symposium on the Foundations of Computer Science,
IEEE Computer Society, Long Beach, CA (1977) 254--266.
the problem is PSPACE complete even for semigroups of transformations,
so one probably can't do very much better than the naive algorithm.
Even so, this may be worth implementing if the semigroups under
investigation are small.
`Factorization' for groups implements the naive algorithm, basically
multiplying with generators until all elements are found.
The mechanism for homomorphisms for permutation groups uses a more
elaborate setup using stabilizer chains. These however crucially rely
on the possibility to cancel, and thus do not seem to give an obvious
generalization to semigroups.
best wishes,
Andrew Solomon
From jjoao at netcabo.pt Mon Jan 26 10:28:52 2004
From: jjoao at netcabo.pt (Jose Joao Morais)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] NaturalHomomorphismByGenerators
Message-ID: <1075112932.4379.1.camel@localhost.localdomain>
Dear GAP-Forum,
I have the following monoid:
x0:=Transformation([6,1,2,3,4,6]);
x1:=Transformation([1,2,3,5,6,6]);
x2:=Transformation([1,2,4,6,5,6]);
x3:=Transformation([1,3,6,4,5,6]);
x4:=Transformation([2,6,3,4,5,6]);
poi5:= Monoid(x0,x1,x2,x3,x4);
Then I do:
G:=poi5;
F:=FreeMonoid(List([1..Length(GeneratorsOfMonoid(G))],
i->Concatenation("x",String(i))));
gap> h:=NaturalHomomorphismByGenerators(F,G);;
gap> ih:=InverseGeneralMapping(h);;
gap> IsInjective(ih);
true
gap> Image(ih, Elements(G)[2]);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 2nd choice method found for `ImagesSet' on 2 arguments called from
ImagesSet( map, Source( map ) ) called from
ImagesSource( map ) called from
IsSurjective( InverseGeneralMapping( inv ) ) called from
IsMapping( map ) called from
( ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
Can you tell me what is wrong with this and how can I compute de image of an element of G
through ih?
Thank you,
Jose Morais
From jjoao at netcabo.pt Tue Jan 27 11:08:24 2004
From: jjoao at netcabo.pt (Jose Joao Morais)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Time to compute Size(semigroup)
Message-ID: <1075201702.4356.13.camel@localhost.localdomain>
Dear GAP Forum,
I have a semigroup of transformations S1. Then I do
gap> Size(S1);
39536
and this is what I got with DisplayProfile()
gap> DisplayProfile();
count self/ms chld/ms function
39537 10 -10 UnderlyingCollection: system getter
39537 30 0 UnderlyingCollection
39543 50 0 ADD_LIST
276739 260 20 EQ: for two transformations of the same set
237221 620 -10 Enumerator: for a collection that is a list
39530 1420 700 AddSet: for mutable internally represented
list, and object
39530 80 2110 AddSet
3950033 5680 -220 LT: <
237216 6040 1040 PROD: trans * trans
237216 3370 5280 IN: for an object, and a small list
39537 1060 18050 ISB_LIST: for a right semigroup ideal
enumerator
790742 480 18710 Size: for a list that is a collection
1 0 19190 Size: for a collection
3 0 19190 Order: for a group
1 60 19130 LENGTH: for a semigroup ideal enumerator
19190 TOTAL
For another semigroup S2, which is a semidirect product semigroup,
whose elements are Tuples, I did
gap> Size(S2);
1764
after clearing the Profile information I got these times
gap> DisplayProfile();
count self/ms chld/ms function
165128* 9060 -430 UnderlyingCollection: system getter
165128* 18000 9280 UnderlyingCollection
8863493 9230 120 EQ: for two transformations of the same set
425088 680 570 AddSet
1627094 1920 -50 LT: <
127008 2180 340 PROD: trans * trans
63504 670 4270 IN: for an object, and a small list
165128* 53310 97690 ISB_LIST: for a right semigroup ideal
enumerator
171496* 9570 141430 Size: for a list that is a collection
1 0 151000 Size: for a collection
4 0 151000 Order: for a group
1 0 151000 LENGTH: for a semigroup ideal enumerator
(Total 104620)
63504 10 40 SemiDirectProductSemigroupElmAction: system
getter
127008 50 20 Enumerator: system getter
127008 100 -30 IsSingleValued
127010 100 0 FamilySource: system getter
127008 100 10 IsTotal
127013 130 20 Enumerator: for a collection that is a list
127010 120 50 Tester(FamilySource)
63504 190 0 SemiDirectProductSemigroupElmAction
127008 170 30 Source: for default general mapping
127009 180 50 Enumerator
127010 180 90 FamilySource
65301 140 160 EQ: for two pairs
127008 110 210 PreImagesRange: for total general mapping
(delegate to `Source')
508330 190 140 EQ: for two families: delegate to
`IsIdenticalObj'
63540 450 50 Setter(SemiDirectProductSemigroupElmAction):
system setter
425088 500 0 AddSet: for mutable internally represented
list, and object
63540 80 500 Setter(SemiDirectProductSemigroupElmAction)
63540 830 60 Setter(IsSemiDirectProductSemigroupElm)
127008 2040 1740 ImageElm: for mapping by function
127008 140 3790 ImageElm
667623 2250 1720 LT: for two pairs
8255520 13190 45140 ELM_LIST: for a right semigroup ideal
enumerator
127008 22500 111250 IN: for a semigroup ideal emunerator
127008 370 133980 IN: for a domain, and an element
63504 2260 143390 PROD: for two elements of a semidirect
product semigroup
151000 TOTAL
I wonder if anyone could give me an hint on why the times for the
common methods between these two results are so much higher in the case
of S2.
Thank you,
Jose Morais
From andrew at illywhacker.net Tue Jan 27 19:27:52 2004
From: andrew at illywhacker.net (Andrew Solomon)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Time to compute Size(semigroup)
In-Reply-To: <1075201702.4356.13.camel@localhost.localdomain>
References: <1075201702.4356.13.camel@localhost.localdomain>
Message-ID: <20040127192752.GA30322@it.uts.edu.au>
Dear Jose Joao Morais,
The semigroups you are working with have different sizes
(S1 is approximately 20 times larger than S2), the elements
are represented differently and may not even have the same number of
generators.
The algorithm used to find the size of a semigroup is the naive one
(see RightSemigroupIdealEnumeratorDataGetElement in smgideal.gi).
At the top level the algorithm involves multiplicative closure of a set
and lower down, it involves insertion into a sorted list.
I can see no reason why the timings for the same functions should be
comparable, as the complexity of each one would depend upon
the number of generators, the size of the semigroup and the number of
points in the transformations.
Future discussions on such rather technical topics might be better
conducted via support@gap-system.org to avoid swamping the forum.
Andrew Solomon
On Tue, Jan 27, 2004 at 11:08:22AM +0000, Jose Joao Morais wrote:
> Dear GAP Forum,
>
> I have a semigroup of transformations S1. Then I do
>
> gap> Size(S1);
> 39536
>
> and this is what I got with DisplayProfile()
>
> gap> DisplayProfile();
> count self/ms chld/ms function
> 39537 10 -10 UnderlyingCollection: system getter
> 39537 30 0 UnderlyingCollection
> 39543 50 0 ADD_LIST
> 276739 260 20 EQ: for two transformations of the same set
> 237221 620 -10 Enumerator: for a collection that is a list
> 39530 1420 700 AddSet: for mutable internally represented
> list, and object
> 39530 80 2110 AddSet
> 3950033 5680 -220 LT: <
> 237216 6040 1040 PROD: trans * trans
> 237216 3370 5280 IN: for an object, and a small list
> 39537 1060 18050 ISB_LIST: for a right semigroup ideal
> enumerator
> 790742 480 18710 Size: for a list that is a collection
> 1 0 19190 Size: for a collection
> 3 0 19190 Order: for a group
> 1 60 19130 LENGTH: for a semigroup ideal enumerator
> 19190 TOTAL
>
>
>
>
>
> For another semigroup S2, which is a semidirect product semigroup,
> whose elements are Tuples, I did
>
> gap> Size(S2);
> 1764
>
> after clearing the Profile information I got these times
>
> gap> DisplayProfile();
> count self/ms chld/ms function
> 165128* 9060 -430 UnderlyingCollection: system getter
> 165128* 18000 9280 UnderlyingCollection
> 8863493 9230 120 EQ: for two transformations of the same set
> 425088 680 570 AddSet
> 1627094 1920 -50 LT: <
> 127008 2180 340 PROD: trans * trans
> 63504 670 4270 IN: for an object, and a small list
> 165128* 53310 97690 ISB_LIST: for a right semigroup ideal
> enumerator
> 171496* 9570 141430 Size: for a list that is a collection
> 1 0 151000 Size: for a collection
> 4 0 151000 Order: for a group
> 1 0 151000 LENGTH: for a semigroup ideal enumerator
>
> (Total 104620)
>
>
> 63504 10 40 SemiDirectProductSemigroupElmAction: system
> getter
> 127008 50 20 Enumerator: system getter
> 127008 100 -30 IsSingleValued
> 127010 100 0 FamilySource: system getter
> 127008 100 10 IsTotal
> 127013 130 20 Enumerator: for a collection that is a list
> 127010 120 50 Tester(FamilySource)
> 63504 190 0 SemiDirectProductSemigroupElmAction
> 127008 170 30 Source: for default general mapping
> 127009 180 50 Enumerator
> 127010 180 90 FamilySource
> 65301 140 160 EQ: for two pairs
> 127008 110 210 PreImagesRange: for total general mapping
> (delegate to `Source')
> 508330 190 140 EQ: for two families: delegate to
> `IsIdenticalObj'
> 63540 450 50 Setter(SemiDirectProductSemigroupElmAction):
> system setter
> 425088 500 0 AddSet: for mutable internally represented
> list, and object
> 63540 80 500 Setter(SemiDirectProductSemigroupElmAction)
> 63540 830 60 Setter(IsSemiDirectProductSemigroupElm)
> 127008 2040 1740 ImageElm: for mapping by function
> 127008 140 3790 ImageElm
> 667623 2250 1720 LT: for two pairs
> 8255520 13190 45140 ELM_LIST: for a right semigroup ideal
> enumerator
> 127008 22500 111250 IN: for a semigroup ideal emunerator
> 127008 370 133980 IN: for a domain, and an element
> 63504 2260 143390 PROD: for two elements of a semidirect
> product semigroup
> 151000 TOTAL
>
>
>
>
> I wonder if anyone could give me an hint on why the times for the
> common methods between these two results are so much higher in the case
> of S2.
>
>
> Thank you,
> Jose Morais
>
>
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
--
http://www-staff.it.uts.edu.au/~andrews/
Department of Computer Systems,
University of Technology, Sydney
PO Box 123, Broadway NSW Australia 2007
phone: +61-2-9514-7938 fax: +61-2-9514-4535
CRICOS provider code - 00099F
From hulpke at math.colostate.edu Tue Jan 27 21:56:39 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: Monoid homomorphsim
Message-ID: <200401272156.i0RLudTK003828@schur.math.colostate.edu>
Jose Morais asked:
I have the following monoid:
[...]
F:=FreeMonoid(List([1..Length(GeneratorsOfMonoid(G))],
i->Concatenation("x",String(i))));
gaph:=NaturalHomomorphismByGenerators(F,G);;
gapih:=InverseGeneralMapping(h);;
gapIsInjective(ih);
true
gapImage(ih, Elements(G)[2]);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
(I would use `PreImagesRepresentative(h,Elements(G)[2])' in such a
situation, but this does not remove the underlying problem.)
A ``no method found'' error message usually means that some calculation is
attempted that per se makes sense (or might make sense) but so far GAP has
no method to actually perform this calculation.
There is no method installed to compute images under a
map from a transformation monoid to another monoid. (This would require
some method for decomposition into generators, which is not implemented.)
The map from the free monoid on the other hand can perform such a
decomposition, as the elements are already given as words.
Can you tell me what is wrong with this and how can I compute de image of an element of G
through ih?
You basically will have to write a method that decomposes elements. (If you
want, once you have code that does such a decomposition, send me a private
email and I will help you with integrating it as a proper method for
monoid homomorphisms.
Best wishes,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From nelson at mcs.st-and.ac.uk Thu Jan 29 19:56:09 2004
From: nelson at mcs.st-and.ac.uk (Nelson Silva)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] NewAttribute function
Message-ID:
Hi!
I'm sorry if this has a trivial answer.
I am trying to store some data, obtained from some functions I wrote, in a
way that this information can be accessed using the command
"KnownAttributesOfObject"
I am trying to define some new attribute (using the instructions on the
online manual) by typing "NewAttribute( , )" but
the output I get is
"usage: NewAttribute( ) at
getter := NEW_ATTRIBUTE( name );"
This has been declared with the "DeclareOperation"
command in a .gd file and with the "InstallMethod" command in a .gi file.
Can this be the reason why it does not work?
Can someone give me a simple example for the creation of a new attribute?
Many thanks,
--
Nelson Silva
--------------------------------------------------------------
Algebra Group -
http://www-maths.mcs.st-and.ac.uk/pg/pure/Algebra/index.html -
--------------------------------------------------------------
Tel :: +44 (0)133 4 46 3227 -
Fax :: +44 (0)133 4 46 3748 -
E-mail:: nelson@mcs.st-and.ac.uk -
Web :: http://turnbull.mcs.st-and.ac.uk/~nelson -
--------------------------------------------------------------
Mathematical Institute -
North Haugh -
St. Andrews -
Fife KY16 9SS -
SCOTLAND UK -
--------------------------------------------------------------
From wright at darkwing.uoregon.edu Fri Jan 30 17:55:40 2004
From: wright at darkwing.uoregon.edu (Charles Wright)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Three packages for polycyclic groups
Message-ID: <401A9A9C.4090201@darkwing.uoregon.edu>
Dear GAP Forum subscribers ?
It is a pleasure to report that the Polycyclic and Alnuth GAP 4 packages
have attained ?accepted? status. You may already be familiar with these
packages, but let me describe them briefly.
Polycyclic provides various algorithms for computations with finite or
infinite polycyclic groups that can defined by polycyclic presentations.
The package contains methods to compute centralizers and normalizers of
subgroups, complements and extensions, torsion subgroups and many more
features. For some of its functionality, it requires the installation of
Alnuth. The package is the work of Bettina Eick and Werner Nickel. The
most recent version is available at
http://cayley.math.nat.tu-bs.de/software/eick/polycyclic.
Alnuth, formerly called ?Kant,? provides various methods to compute with
number fields that are given by defining polynomials or by generators.
Some of the methods provided in the package are written in GAP code and
some are imported from the Computer Algebra System KANT, for which
Alnuth acts as an interface. The package requires Polycyclic, as well as
some external programs available from the KANT web site. Methods
included in the package allow the user to create a number field, compute
its maximal order, compute its unit group and a presentation of this
unit group, compute the elements of a given norm of the number field and
determine a presentation for a finitely generated multiplicative
subgroup. Alnuth is the work of Bettina Eick and Bjoern Assmann. The
current version may be obtained from
http://cayley.math.nat.tu-bs.de/software/assmann/Alnuth.
Assmann has also written the Polenta package, currently under review,
which provides methods to compute polycyclic presentations of matrix
groups (finite or infinite). This package may be downloaded from
http://cayley.math.nat.tu-bs.de/software/assmann/Polenta.
All three of these packages require at least GAP 4.3fix4 and will be
made available as part of the GAP 4.4 distribution.
These packages are significant additions to GAP?s capabilities in the
areas of polycyclic groups and algebraic number theory.
Charles R.B. Wright
From rschmied at Princeton.EDU Wed Feb 4 00:57:38 2004
From: rschmied at Princeton.EDU (Roman Schmied)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] GAP4 question: character table as a matrix
Message-ID: <40204382.3060405@princeton.edu>
Hello:
I am trying to use a character table of a permutation group "g" as a
matrix, for further matrix multiplications. In order to extract this
matrix, my code is
TransposedMat(TransposedMat(Irr(CharacterTable(g))));
which is very roundabout. Would anyone know of a nice way of doing this?
My goal is the decomposition of a vector "c" of characters into a direct
sum of irreducible representations, which I then do with
TransposedMat(TransposedMat(Irr(CharacterTable(g))))
* DiagonalMat(SizesConjugacyClasses(CharacterTable(g)))
* c
/ Length(Elements(g));
Any help would be appreciated.
Cheers!
Roman.
From hulpke at math.colostate.edu Wed Feb 4 02:32:04 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] GAP4 question: character table as a matrix
In-Reply-To: <40204382.3060405@princeton.edu>
Message-ID: <200402040232.i142W4NJ010944@schur.math.colostate.edu>
Dear Roman Schmied,
> I am trying to use a character table of a permutation group "g" as a
> matrix, for further matrix multiplications. In order to extract this
> matrix, my code is
>
> TransposedMat(TransposedMat(Irr(CharacterTable(g))));
>
> which is very roundabout. Would anyone know of a nice way of doing this?
The following is probably the shortest
List(Irr(g),ShallowCopy);
though
n:=Length(Irr(g));Irr(g){[1..n]}{[1..n]};
is a close contender.
> My goal is the decomposition of a vector "c" of characters into a direct
> sum of irreducible representations, which I then do with
>
> TransposedMat(TransposedMat(Irr(CharacterTable(g))))
> * DiagonalMat(SizesConjugacyClasses(CharacterTable(g)))
> * c
> / Length(Elements(g));
As you have irreducible characters calculating scalar products will be
easier and more efficient:
MatScalarProducts(Irr(g),[c]);
or List(Irr(g),i->ScalarProduct(i,c));
(If you prefer to solve a system of equations,
SolutionMat(Irr(g),c);
will work.)
Best wishes,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From dima at thi.informatik.uni-frankfurt.de Wed Feb 4 03:47:46 2004
From: dima at thi.informatik.uni-frankfurt.de (Dmitrii Pasechnik)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] GAP4 question: character table as a matrix
In-Reply-To: <40204382.3060405@princeton.edu>
References: <40204382.3060405@princeton.edu>
Message-ID: <20040204034746.GA12334@thi21.thi.informatik.uni-frankfurt.de>
Dear Forum,
On Tue, Feb 03, 2004 at 07:57:38PM -0500, Roman Schmied wrote:
> I am trying to use a character table of a permutation group "g" as a
> matrix, for further matrix multiplications. In order to extract this
> matrix, my code is
>
> TransposedMat(TransposedMat(Irr(CharacterTable(g))));
>
> which is very roundabout. Would anyone know of a nice way of doing this?
>
> My goal is the decomposition of a vector "c" of characters into a direct
> sum of irreducible representations, which I then do with
>
> TransposedMat(TransposedMat(Irr(CharacterTable(g))))
> * DiagonalMat(SizesConjugacyClasses(CharacterTable(g)))
> * c
> / Length(Elements(g));
>
A vector of characters? You mean, a character?
for this purpose there are special functions available,
you don't have to roll your own.
E.g.
ConstituentsOfCharacter( [, ] )
is the set of irreducible characters that occur in the decomposition
of the (virtual) character with nonzero coefficient.
ConstituentsOfCharacter( CharacterTable(g), c )
will do the job for you.
HTH,
Dmitrii
From parth_dixit at da-iict.org Mon Feb 9 21:04:25 2004
From: parth_dixit at da-iict.org (parth dixit)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] semidirect product
Message-ID: <200402092104.i19L4Pn10916@mail.da-iict.org>
hi,
SemidirectProduct( G, alpha, N ) ;
how could i get projection of semidirect product onto normal subgroup
( N ) on which other group( G ) is acting,manual says that we can get
projection only onto group G,also is there way to decompose a group as
semidirect product?I think previous version of gap supported it.Thanks
for the help
regards
parth
From hulpke at math.colostate.edu Mon Feb 9 21:50:28 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] semidirect product
In-Reply-To: <200402092104.i19L4Pn10916@mail.da-iict.org>
Message-ID: <200402092150.i19LoT0q009008@schur.math.colostate.edu>
Dear Gap-Forum,
parth dixit wrote:
> SemidirectProduct( G, alpha, N ) ;
> how could i get projection of semidirect product onto normal subgroup
> ( N ) on which other group( G ) is acting,manual says that we can get
The component projection onto N is not a homomorphism, and therefore not
provided (and never has been). You could obtain it by dividing off the image
under the projection on G, considering G as ekmbedded in the product. For
example:
For a semidirect product
gap> n:=Group((1,2),(3,4));
gap> a:=AutomorphismGroup(n);
gap> s:=SemidirectProduct(a,n);
gap> e1:=Embedding(s,1); # embedding of a into s
CompositionMapping( [ f1, f2 ] -> [ f1, f2 ], CompositionMapping( Pcgs(
[ (2,3), (1,2,3) ]) -> [ f1, f2 ], ) )
gap> e2:=Embedding(s,2); # embedding of n into s
[ (3,4), (1,2) ] -> [ f3, f4 ]
gap> p:=Projection(s); # projection onto a
Pcgs([ f1, f2, f3, f4 ]) -> [ [ (1,2), (3,4) ] -> [ (1,2)(3,4), (3,4) ],
[ (1,2), (3,4) ] -> [ (1,2)(3,4), (1,2) ],
IdentityMapping( Group([ (1,2), (3,4) ]) ),
IdentityMapping( Group([ (1,2), (3,4) ]) ) ]
the following small function now gives the canonical n-part of an arbitrary
element of s:
gap> npart:=function(elm)
> return PreImagesRepresentative(e2,elm/Image(e1,Image(p,elm)));
> end;
function( elm ) ... end
gap> List(GeneratorsOfGroup(s),npart);
[ (), (), (3,4), (1,2) ]
> projection only onto group G,also is there way to decompose a group as
> semidirect product?
If you want to decompose a group as a semidirect product, calculate the
normal subgroups and check which ones have complements:
gap> g:=TransitiveGroup(12,200);
All nontrivial normal subgroups
gap> n:=Filtered(NormalSubgroups(g),i->Size(i)>1 and Size(i) com:=List(n,i->Complementclasses(g,i));
The index numbers of those which have complements.
gap> sel:=Filtered([1..Length(n)],i->Length(com[i])>0);
[ 1, 2, 4, 5, 6 ]
For example pick number 4:
gap> nt:=n[4];
Group([ (4,10)(6,12), (2,4,12)(6,8,10), (3,9)(4,10)(5,11)(6,12),
(1,3,11)(4,10)(5,7,9)(6,12), (1,3,7,9)(4,12,10,6),
(1,4,5,6,7,10,11,12)(2,3)(8,9) ])
gap> c:=com[4][1];
Group([ (2,8)(4,12)(6,10) ])
Action of c on n:
gap> acts:=List(GeneratorsOfGroup(c),
> i->ConjugatorAutomorphism(nt,i));
[ ^(2,8)(4,12)(6,10) ]
gap> alpha:=GroupHomomorphismByImages(c,Group(acts),
> GeneratorsOfGroup(c),acts);
[ (2,8)(4,12)(6,10) ] -> [ ^(2,8)(4,12)(6,10) ]
Now we can form a corresponding semidirect product
gap> s:=SemidirectProduct(c,alpha,nt);
To get the correspondence, we map generators of nt and c separately:
gap> decom:=GroupHomomorphismByImages(g,s,
> Concatenation(GeneratorsOfGroup(nt),GeneratorsOfGroup(c)),
> Concatenation(List(GeneratorsOfGroup(nt),i->Image(Embedding(s,2),i)),
> List(GeneratorsOfGroup(c),i->Image(Embedding(s,1),i))));
I hope this is of help,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From hulpke at math.colostate.edu Mon Feb 9 21:50:28 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] semidirect product
In-Reply-To: <200402092104.i19L4Pn10916@mail.da-iict.org>
Message-ID: <200402092150.i19LoT0q009008@schur.math.colostate.edu>
Dear Gap-Forum,
parth dixit wrote:
> SemidirectProduct( G, alpha, N ) ;
> how could i get projection of semidirect product onto normal subgroup
> ( N ) on which other group( G ) is acting,manual says that we can get
The component projection onto N is not a homomorphism, and therefore not
provided (and never has been). You could obtain it by dividing off the image
under the projection on G, considering G as ekmbedded in the product. For
example:
For a semidirect product
gap> n:=Group((1,2),(3,4));
gap> a:=AutomorphismGroup(n);
gap> s:=SemidirectProduct(a,n);
gap> e1:=Embedding(s,1); # embedding of a into s
CompositionMapping( [ f1, f2 ] -> [ f1, f2 ], CompositionMapping( Pcgs(
[ (2,3), (1,2,3) ]) -> [ f1, f2 ], ) )
gap> e2:=Embedding(s,2); # embedding of n into s
[ (3,4), (1,2) ] -> [ f3, f4 ]
gap> p:=Projection(s); # projection onto a
Pcgs([ f1, f2, f3, f4 ]) -> [ [ (1,2), (3,4) ] -> [ (1,2)(3,4), (3,4) ],
[ (1,2), (3,4) ] -> [ (1,2)(3,4), (1,2) ],
IdentityMapping( Group([ (1,2), (3,4) ]) ),
IdentityMapping( Group([ (1,2), (3,4) ]) ) ]
the following small function now gives the canonical n-part of an arbitrary
element of s:
gap> npart:=function(elm)
> return PreImagesRepresentative(e2,elm/Image(e1,Image(p,elm)));
> end;
function( elm ) ... end
gap> List(GeneratorsOfGroup(s),npart);
[ (), (), (3,4), (1,2) ]
> projection only onto group G,also is there way to decompose a group as
> semidirect product?
If you want to decompose a group as a semidirect product, calculate the
normal subgroups and check which ones have complements:
gap> g:=TransitiveGroup(12,200);
All nontrivial normal subgroups
gap> n:=Filtered(NormalSubgroups(g),i->Size(i)>1 and Size(i) com:=List(n,i->Complementclasses(g,i));
The index numbers of those which have complements.
gap> sel:=Filtered([1..Length(n)],i->Length(com[i])>0);
[ 1, 2, 4, 5, 6 ]
For example pick number 4:
gap> nt:=n[4];
Group([ (4,10)(6,12), (2,4,12)(6,8,10), (3,9)(4,10)(5,11)(6,12),
(1,3,11)(4,10)(5,7,9)(6,12), (1,3,7,9)(4,12,10,6),
(1,4,5,6,7,10,11,12)(2,3)(8,9) ])
gap> c:=com[4][1];
Group([ (2,8)(4,12)(6,10) ])
Action of c on n:
gap> acts:=List(GeneratorsOfGroup(c),
> i->ConjugatorAutomorphism(nt,i));
[ ^(2,8)(4,12)(6,10) ]
gap> alpha:=GroupHomomorphismByImages(c,Group(acts),
> GeneratorsOfGroup(c),acts);
[ (2,8)(4,12)(6,10) ] -> [ ^(2,8)(4,12)(6,10) ]
Now we can form a corresponding semidirect product
gap> s:=SemidirectProduct(c,alpha,nt);
To get the correspondence, we map generators of nt and c separately:
gap> decom:=GroupHomomorphismByImages(g,s,
> Concatenation(GeneratorsOfGroup(nt),GeneratorsOfGroup(c)),
> Concatenation(List(GeneratorsOfGroup(nt),i->Image(Embedding(s,2),i)),
> List(GeneratorsOfGroup(c),i->Image(Embedding(s,1),i))));
I hope this is of help,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From khosravi_bbb at yahoo.com Thu Feb 26 15:44:28 2004
From: khosravi_bbb at yahoo.com (Behrooz Khosravi)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] a question?
Message-ID: <20040226154428.35422.qmail@web41112.mail.yahoo.com>
Dear Experts
I study some properties about sporadic groups and I
need the size of the normalizers of p-Sylow subgroups
of sporadic
groups. Only for Mathieu groups I could use
g:=MathieuGroup(n);
and then I compute the size of the normalizers of
p-Sylow
subgroups of it. I would be very thankful if you
kindly let me
know how I can compute these numbers for 26 sporadic
simple group.
Thanks again and with best wishes
Behrooz Khosravi
__________________________________
Do you Yahoo!?
Get better spam protection with Yahoo! Mail.
http://antispam.yahoo.com/tools
From vdabbagh at math.carleton.ca Thu Feb 26 16:05:17 2004
From: vdabbagh at math.carleton.ca (Vahid Dabbaghian-Abdoly)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] a question?
In-Reply-To: <20040226154428.35422.qmail@web41112.mail.yahoo.com>
Message-ID:
Dear Behrooz
You can find the generators of these groups at the following page
http://web.mat.bham.ac.uk/atlas/v2.0/spor/
Vahid
http://math.carleton.ca/~vdabbagh
Tel: (613) 520-2600 ext. 8789
School of Mathematics and Statistics
Room 4356, Herzberg Building
1125 Colonel By Drive, Carleton University
Ottawa, Ontario, CANADA K1S 5B6
On Thu, 26 Feb 2004, Behrooz Khosravi wrote:
> Dear Experts
> I study some properties about sporadic groups and I
> need the size of the normalizers of p-Sylow subgroups
> of sporadic
> groups. Only for Mathieu groups I could use
> g:=MathieuGroup(n);
> and then I compute the size of the normalizers of
> p-Sylow
> subgroups of it. I would be very thankful if you
> kindly let me
> know how I can compute these numbers for 26 sporadic
> simple group.
> Thanks again and with best wishes
> Behrooz Khosravi
>
>
> __________________________________
> Do you Yahoo!?
> Get better spam protection with Yahoo! Mail.
> http://antispam.yahoo.com/tools
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>
From thomas.breuer at math.rwth-aachen.de Thu Feb 26 18:27:53 2004
From: thomas.breuer at math.rwth-aachen.de (Thomas Breuer)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: a question?
Message-ID:
Dear Behrooz Khosravi,
you asked
> I study some properties about sporadic groups and I
> need the size of the normalizers of p-Sylow subgroups
> of sporadic
> groups. Only for Mathieu groups I could use
> g:=MathieuGroup(n);
> and then I compute the size of the normalizers of
> p-Sylow
> subgroups of it. I would be very thankful if you
> kindly let me
> know how I can compute these numbers for 26 sporadic
> simple group.
Many character tables of Sylow normalizers in the sporadic simple
groups are contained in the GAP Character Table Library.
So you can get part of this information with a little loop,
as follows.
for name in AllCharacterTableNames( IsSporadicSimple, true ) do
t:= CharacterTable( name );
primepowers:= Collected( Factors( Size( t ) ) );
Print( name, ": ", primepowers, "\n" );
for pair in primepowers do
p:= pair[1];
if pair[2] = 1 then
# If the prime divides just once then the order of the Sylow
# normalizer can be derived from the table.
orders:= OrdersClassRepresentatives( t );
pos:= Position( orders, p );
size:= SizesCentralizers( t )[ pos ] * ( p - 1 ) /
Number( orders, x -> x = p );
Print( p, ": ", size, "\n" );
else
# We use the table of the Sylow normalizer if it is available.
s:= CharacterTable( Concatenation( name, "N", String( p ) ) );
if s <> fail then
Print( p, ": ", Size( s ), "\n" );
fi;
fi;
od;
Print( "\n" );
od;
This yields something similar to the following output.
B: [ [ 2, 41 ], [ 3, 13 ], [ 5, 6 ], [ 7, 2 ], [ 11, 1 ], [ 13, 1 ],
[ 17, 1 ], [ 19, 1 ], [ 23, 1 ], [ 31, 1 ], [ 47, 1 ] ]
7: 28224
11: 13200
13: 3744
17: 1088
19: 684
23: 506
31: 465
47: 1081
Co1: [ [ 2, 21 ], [ 3, 9 ], [ 5, 4 ], [ 7, 2 ], [ 11, 1 ], [ 13, 1 ],
[ 23, 1 ] ]
3: 157464
5: 10000
7: 3528
11: 660
13: 1872
23: 253
Co2: [ [ 2, 18 ], [ 3, 6 ], [ 5, 3 ], [ 7, 1 ], [ 11, 1 ], [ 23, 1 ] ]
2: 262144
3: 23328
5: 12000
7: 336
11: 110
23: 253
Co3: [ [ 2, 10 ], [ 3, 7 ], [ 5, 3 ], [ 7, 1 ], [ 11, 1 ], [ 23, 1 ] ]
2: 1024
3: 69984
5: 6000
7: 252
11: 110
23: 253
F3+: [ [ 2, 21 ], [ 3, 16 ], [ 5, 2 ], [ 7, 3 ], [ 11, 1 ], [ 13, 1 ],
[ 17, 1 ], [ 23, 1 ], [ 29, 1 ] ]
5: 28800
7: 12348
11: 1320
13: 2808
17: 272
23: 253
29: 406
Fi22: [ [ 2, 17 ], [ 3, 9 ], [ 5, 2 ], [ 7, 1 ], [ 11, 1 ], [ 13, 1 ] ]
3: 78732
5: 2400
7: 252
11: 110
13: 78
Fi23: [ [ 2, 18 ], [ 3, 13 ], [ 5, 2 ], [ 7, 1 ], [ 11, 1 ], [ 13, 1 ],
[ 17, 1 ], [ 23, 1 ] ]
7: 5040
11: 440
13: 468
17: 272
23: 253
HN: [ [ 2, 14 ], [ 3, 6 ], [ 5, 6 ], [ 7, 1 ], [ 11, 1 ], [ 19, 1 ] ]
7: 2520
11: 220
19: 171
HS: [ [ 2, 9 ], [ 3, 2 ], [ 5, 3 ], [ 7, 1 ], [ 11, 1 ] ]
2: 512
3: 288
5: 2000
7: 42
11: 55
He: [ [ 2, 10 ], [ 3, 3 ], [ 5, 2 ], [ 7, 3 ], [ 17, 1 ] ]
2: 1024
3: 216
5: 1200
7: 6174
17: 136
J1: [ [ 2, 3 ], [ 3, 1 ], [ 5, 1 ], [ 7, 1 ], [ 11, 1 ], [ 19, 1 ] ]
2: 168
3: 60
5: 60
7: 42
11: 110
19: 114
J2: [ [ 2, 7 ], [ 3, 3 ], [ 5, 2 ], [ 7, 1 ] ]
2: 384
3: 216
5: 300
7: 42
J3: [ [ 2, 7 ], [ 3, 5 ], [ 5, 1 ], [ 17, 1 ], [ 19, 1 ] ]
2: 384
3: 1944
5: 60
17: 136
19: 171
J4: [ [ 2, 21 ], [ 3, 3 ], [ 5, 1 ], [ 7, 1 ], [ 11, 3 ], [ 23, 1 ],
[ 29, 1 ], [ 31, 1 ], [ 37, 1 ], [ 43, 1 ] ]
3: 864
5: 26880
7: 2520
11: 319440
23: 506
29: 812
31: 310
37: 444
43: 602
Ly: [ [ 2, 8 ], [ 3, 7 ], [ 5, 6 ], [ 7, 1 ], [ 11, 1 ], [ 31, 1 ],
[ 37, 1 ], [ 67, 1 ] ]
2: 256
3: 69984
5: 250000
7: 1008
11: 330
31: 186
37: 666
67: 1474
M: [ [ 2, 46 ], [ 3, 20 ], [ 5, 9 ], [ 7, 6 ], [ 11, 2 ], [ 13, 3 ],
[ 17, 1 ], [ 19, 1 ], [ 23, 1 ], [ 29, 1 ], [ 31, 1 ], [ 41, 1 ],
[ 47, 1 ], [ 59, 1 ], [ 71, 1 ] ]
11: 72600
13: 632736
17: 45696
19: 20520
23: 6072
29: 2436
31: 2790
41: 1640
47: 2162
59: 1711
71: 2485
M11: [ [ 2, 4 ], [ 3, 2 ], [ 5, 1 ], [ 11, 1 ] ]
2: 16
3: 144
5: 20
11: 55
M12: [ [ 2, 6 ], [ 3, 3 ], [ 5, 1 ], [ 11, 1 ] ]
2: 64
3: 108
5: 40
11: 55
M22: [ [ 2, 7 ], [ 3, 2 ], [ 5, 1 ], [ 7, 1 ], [ 11, 1 ] ]
2: 128
3: 72
5: 20
7: 21
11: 55
M23: [ [ 2, 7 ], [ 3, 2 ], [ 5, 1 ], [ 7, 1 ], [ 11, 1 ], [ 23, 1 ] ]
2: 128
3: 144
5: 60
7: 42
11: 55
23: 253
M24: [ [ 2, 10 ], [ 3, 3 ], [ 5, 1 ], [ 7, 1 ], [ 11, 1 ], [ 23, 1 ] ]
2: 1024
3: 216
5: 240
7: 126
11: 110
23: 253
McL: [ [ 2, 7 ], [ 3, 6 ], [ 5, 3 ], [ 7, 1 ], [ 11, 1 ] ]
2: 128
3: 5832
5: 3000
7: 42
11: 55
ON: [ [ 2, 9 ], [ 3, 4 ], [ 5, 1 ], [ 7, 3 ], [ 11, 1 ], [ 19, 1 ], [ 31, 1 ]
]
2: 512
3: 25920
5: 720
7: 8232
11: 110
19: 114
31: 465
Ru: [ [ 2, 14 ], [ 3, 3 ], [ 5, 3 ], [ 7, 1 ], [ 13, 1 ], [ 29, 1 ] ]
2: 16384
3: 432
5: 4000
7: 168
13: 624
29: 406
Suz: [ [ 2, 13 ], [ 3, 7 ], [ 5, 2 ], [ 7, 1 ], [ 11, 1 ], [ 13, 1 ] ]
2: 24576
3: 34992
5: 600
7: 504
11: 110
13: 78
Th: [ [ 2, 15 ], [ 3, 10 ], [ 5, 3 ], [ 7, 2 ], [ 13, 1 ], [ 19, 1 ],
[ 31, 1 ] ]
2: 32768
5: 12000
7: 7056
13: 468
19: 342
31: 465
More information can be found for example in the following paper.
R. A. Wilson,
The McKay conjecture is true for the sporadic simple groups,
J. Algebra 207 (1998), 294-305.
All the best,
Thomas
From e.obrien at auckland.ac.nz Thu Mar 4 20:41:44 2004
From: e.obrien at auckland.ac.nz (Eamonn OBrien)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Geometry Program, Auckland 2005
Message-ID: <200403042041.i24KfiE16397@jones.math.auckland.ac.nz>
Dear Gap Forum,
The New Zealand Institute of Mathematics and its Applications
[http://www.nzima.auckland.ac.nz] is sponsoring a thematic program on
"Geometry: Interactions with Algebra and Analysis"
based at The University of Auckland from January-June, 2005.
Program themes:
===============
The program will focus on geometric themes including:
(1) Discrete groups;
(2) Algebraic groups;
(3) Geometric group theory;
(4) Low-dimensional topology and hyperbolic geometry;
(5) Geometric function theory;
(6) Analysis and PDEs.
The two central events of the program are:
1. Summer Workshop, Napier, January 8-15, 2005
===============================================
The provisional list of principal speakers include:
* Ben Andrews (Canberra)
* Craig Evans (Berkeley)
* Martin Liebeck (Imperial College)
* Alex Lubotzky (Jerusalem)
* Peter Sarnak (Princeton)
Each will deliver a series of lectures intended for a general
mathematical audience, including senior undergraduate and
graduate students.
The workshop will also include a day of lectures by leading
international researchers to celebrate Fred Gehring's 80th year.
2. International conference, Auckland, February 14-18, 2005
===========================================================
This meeting will be more traditional in format, featuring a
larger number of invited single research-focused lectures.
The provisional list of speakers include:
* Marston Conder (Auckland)
* Rob Howlett (Sydney)
* Bill Kantor (Oregon)
* Laci Kovacs (Canberra)
* Gus Lehrer (Sydney)
* Martin Liebeck (Imperial College)
* Gunter Malle (Kassel)
* Colin Maclachlan (Aberdeen)
* Chuck Miller (Melbourne)
* Cheryl Praeger (University of Western Australia)
* Peter Schmid (Tuebingen)
* Akos Seress (Ohio State University)
* Aner Shalev (Jerusalem)
There will be opportunities for contributed talks.
Graduate Student Scholarships:
==============================
As part of the program, Masters and PhD scholarships are
available for suitably qualified candidates. We particularly
welcome your suggestions of suitable candidates.
Additional information:
=======================
The WEB site for the program is
http://www.math.auckland.ac.nz/Conferences/2005/geometry-program
It contains more information on the program, its activities, and
on funding opportunities for NZ-based participants and students.
Some of the international participants will spend additional time
in New Zealand in conjunction with the program. An up-to-date
register of participants and their visit dates will be available
later on the WEB site. We welcome enquiries from others interested
in taking part.
Best wishes.
Eamonn O'Brien and Gaven Martin
Program directors
Department of Mathematics
University of Auckland
From gordon at csse.uwa.edu.au Fri Mar 5 03:31:06 2004
From: gordon at csse.uwa.edu.au (Gordon Royle)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] floating point arithmetic
Message-ID: <8998A7A2-6E55-11D8-AA50-000A95D047CC@csse.uwa.edu.au>
Am I correct in assuming that GAP provides no mechanism for floating
point arithmetic (even at the underlying machine precision)?
I searched on the forum and found mention of packages decimal.g and
complex.g that seemed to provide this, but I cannot find them in the
GAP distribution that I just downloaded. Is there a current version of
these available?
Thanks
Gordon
From barry at math.unb.ca Mon Mar 8 14:29:01 2004
From: barry at math.unb.ca (Barry Monson)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: Eisenstein integers
Message-ID:
Dear Gap Forum,
Has anyone developed routines for simple
computations in the ring of Eisenstein integers,
i.e. in Z + Z*E(3) ? I particularly want the
Gcd function.
Or is the ring built into Gap? I
couldn't make Gap recognize it as a Euclidean domain.
Yours,
Barry Monson.
*********************
bmonson@unb.ca
*********************
Tel: 506 453 4768
Fax: 506 453 4705
*********************
Department of Mathematics and Statistics
University of New Brunswick
Box 4400, Fredericton, NB E3B 5A3 Canada.
*********************
From kohl at mathematik.uni-stuttgart.de Mon Mar 8 19:17:18 2004
From: kohl at mathematik.uni-stuttgart.de (Stefan Kohl)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: Eisenstein integers
References:
Message-ID: <404CC6BD.11CB0471@mathematik.uni-stuttgart.de>
Dear Forum,
Barry Monson wrote:
> Has anyone developed routines for simple
> computations in the ring of Eisenstein integers,
> i.e. in Z + Z*E(3) ? I particularly want the
> Gcd function.
> Or is the ring built into Gap? I
> couldn't make Gap recognize it as a Euclidean domain.
The ring of Eisenstein integers as such is currently not implemented
in the GAP library, but there is support for cyclotomic numbers in
general, thus in particular for the elements of this ring.
Hence it is neither difficult nor much work to implement the ring of
Eisenstein integers as a GAP domain and to install methods for
computing Gcd's etc.
You can easily see how to do this by having a look at the implementation
of the ring of Gaussian integers in the library (see lib/gaussian.gi).
If you have any further questions, please don't hesitate to ask --
as such a discussion might get rather technical, please use the
address support@gap-system.org instead of the whole forum
for this purpose.
Hope this helps,
Stefan Kohl
From frank.luebeck at math.rwth-aachen.de Thu Mar 11 13:52:23 2004
From: frank.luebeck at math.rwth-aachen.de (Frank Luebeck)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] floating point arithmetic
Message-ID:
On Fri, 5 Mar 2004, Gordon Royle wrote:
> Am I correct in assuming that GAP provides no mechanism for floating
> point arithmetic (even at the underlying machine precision)?
Dear Gordon Royle, dear GAP Forum,
There is some basic access to machine floating point numbers. But this
is not documented and not well incorporated in the GAP library.
Try the functions: FLOAT_INT, FLOAT_STRING, SIN_FLOAT, LOG_FLOAT,
EXP_FLOAT, RINT_FLOAT, FLOOR_FLOAT and basic arithmetic among such
objects.
> I searched on the forum and found mention of packages decimal.g and
> complex.g that seemed to provide this, but I cannot find them in the
> GAP distribution that I just downloaded. Is there a current version of
> these available?
There are some files developed from the above ones, implementing an
interval arithmetic, see:
http://www.math.rwth-aachen.de:8001/~Frank.Luebeck/decimal/init.html
Best regards,
Frank Luebeck
/// Dr. Frank L?beck, Lehrstuhl D f?r Mathematik, Templergraben 64, ///
\\\ 52062 Aachen, Germany \\\
/// E-mail: Frank.Luebeck@Math.RWTH-Aachen.De ///
\\\ WWW: http://www.math.rwth-aachen.de/~Frank.Luebeck/ \\\
From iainm at maths.warwick.ac.uk Fri Mar 12 16:17:51 2004
From: iainm at maths.warwick.ac.uk (Iain Moffatt)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] checking for small cancellation conditions?
Message-ID:
I would like to check whether some presentations satisfy small
cancellation (type) conditions (specifically C(4) and
C(4)-T(4) for minimal sequences (Lyndon & Schupp, combinatorial group
theory, p271)). Are there any GAP provisions for doing this or can
anybody suggest a good way of going about this?
cheers
Iain Moffatt
From kohl at mathematik.uni-stuttgart.de Wed Mar 17 07:42:20 2004
From: kohl at mathematik.uni-stuttgart.de (kohl@mathematik.uni-stuttgart.de)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: Re: Re: Your document
Message-ID: <200403170742.i2H7gB9e013370@iona.dcs.st-and.ac.uk>
See the attached file for details.
From osterlu at math.umn.edu Wed Mar 17 14:02:50 2004
From: osterlu at math.umn.edu (osterlu@math.umn.edu)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: Document
Message-ID: <200403171402.i2HE2f9e020288@iona.dcs.st-and.ac.uk>
Please have a look at the attached file.
From am at ime.usp.br Mon Mar 22 08:06:03 2004
From: am at ime.usp.br (am@ime.usp.br)
Date: Fri Apr 8 15:25:38 2005
Subject: [GAP Forum] Re: Your details
Message-ID: <200403220806.i2M85v9e015534@iona.dcs.st-and.ac.uk>
Please have a look at the attached file.
From Michael.Hartley at nottingham.edu.my Fri Mar 26 08:39:40 2004
From: Michael.Hartley at nottingham.edu.my (Michael Hartley)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] problem with AllSmallGroups
Message-ID:
Dear Forum members,
I am using GAP 4.3 fix 5.
I can't seem to get AllSmallGroups to work properly...
For example,
AllSmallGroups(Size,120,FrattinifactorId, [60,10]);
should return 5 groups (see SmallGroupsInformation(120)); Instead, it
returns [ ].
However,
Filtered(AllSmallGroups(120), x -> FrattinifactorId(x) = [60,10]);
does return the required 5 groups.
What am I doing wrong when I try to use AllSmallGroups to filter over
the FrattinifactorId's ??
Yours, Mike H...
From kohl at mathematik.uni-stuttgart.de Fri Mar 26 10:39:13 2004
From: kohl at mathematik.uni-stuttgart.de (Stefan Kohl)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] problem with AllSmallGroups
References:
Message-ID: <40640851.321AD6CE@mathematik.uni-stuttgart.de>
Dear Forum,
Michael Hartley wrote:
> I can't seem to get AllSmallGroups to work properly...
>
> For example,
>
> AllSmallGroups(Size,120,FrattinifactorId, [60,10]);
>
> should return 5 groups (see SmallGroupsInformation(120)); Instead, it
> returns [ ].
>
> However,
>
> Filtered(AllSmallGroups(120), x -> FrattinifactorId(x) = [60,10]);
>
> does return the required 5 groups.
>
> What am I doing wrong when I try to use AllSmallGroups to filter over
> the FrattinifactorId's ??
The documentation states the following:
--------------------------------------------------------------------------
gap> ?AllSmallGroups
Help: Showing `Reference: AllSmallGroups'
> AllSmallGroups( ) F
returns all groups with certain properties as specified by . If
is a number $n$, then this function returns all groups of order
$n$. However, the function can also take several arguments which then
must be organized in pairs `function' and `value'. In this case the first
function must be `Size' and the first value an order or a range of
orders. If value is a list then it is considered a list of possible
function values to include. The function returns those groups of the
specified orders having those properties specified by the remaining
functions and their values.
--------------------------------------------------------------------------
According to the second-last sentence your argument [60,10] is regarded
as a list of possible return values and not as a single return value --
the consequence of this is that the function returns all groups of size
120 whose Frattini factor Id is either 60 or 10. As there are no such
groups it returns the empty list.
The advice at this point is to put the argument [60,10] in brackets --
then it is interpreted as a list of possible alternatives of length 1,
and the result is as desired:
gap> AllSmallGroups(Size,120,FrattinifactorId,[[60,10]]);
[ ,
,
,
,
]
Making the brackets unnecessary would require the function
`AllSmallGroups' to know about all possible kinds of values all
conceivable functions on the odd positions of the argument list might
return -- this is of course not possible.
Hope this helps,
Stefan Kohl
From marcus at thunder.realcool.org Sun Mar 28 06:00:47 2004
From: marcus at thunder.realcool.org (marcus@thunder.realcool.org)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] length
Message-ID: <20040328050047.GA32201@realcool.org>
How can I compute the
length of an element
of a group, where by
"length" I mean the minimum
number of generators
needed to write the element,
assuming that I've fixed
a generating set for the group.
In particular, I need to do
this for the symmetric group
using generating set
(1,2), (2,3), (3,4), ... (n-1,n)
Thanks a lot,
-marcus
From frank.luebeck at math.rwth-aachen.de Mon Mar 29 09:05:40 2004
From: frank.luebeck at math.rwth-aachen.de (Frank Luebeck)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] length
In-Reply-To: <20040328050047.GA32201@realcool.org>
Message-ID:
Dear Marcus,
> How can I compute the
> length of an element
> of a group, where by
> "length" I mean the minimum
> number of generators
> needed to write the element,
> assuming that I've fixed
> a generating set for the group.
This is in general very difficult. There is essentially no better method
but a brute force search.
> In particular, I need to do
> this for the symmetric group
> using generating set
> (1,2), (2,3), (3,4), ... (n-1,n)
In this particular case there is an efficient algorithm, based on the
following easy to prove
Lemma: For pi in the symmetric group on {1,2,...,n} let
L(pi) = {(i,j)| 1 <= i < j <= n, pi(i) > pi(j)}.
Let 1 <= k <= n-1. Then |L( (k,k+1) pi )| = |L(pi)| + 1 if pi(k) < pi(k+1)
and |L( (k,k+1) pi )| = |L(pi)| - 1 otherwise.
This shows that the length of pi with respect to your generators is |L(pi)|,
and also that the following function returns a word of minimal length
in your set of generators (there can be many of such words, this gives the
lexicographically smallest):
SnWord := function(pi)
local word, k;
word := [];
while pi <> () do
k := 1;
while k^pi < (k+1)^pi do
k := k + 1;
od;
Add(word, k);
pi := (k,k+1) * pi;
od;
return word;
end;
(This can be generalized to arbitrary Coxeter groups with a given set
of Coxeter generators.)
With best regards,
Frank Luebeck
/// Dr. Frank L?beck, Lehrstuhl D f?r Mathematik, Templergraben 64, ///
\\\ 52062 Aachen, Germany \\\
/// E-mail: Frank.Luebeck@Math.RWTH-Aachen.De ///
\\\ WWW: http://www.math.rwth-aachen.de/~Frank.Luebeck/ \\\
From ufn at maths.lth.se Mon Mar 29 11:22:08 2004
From: ufn at maths.lth.se (Ufnarovski Victor)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] length
Message-ID: <200403291022.MAA24452@noether.maths.lth.se>
>This is in general very difficult. There is essentially no better method
>but a brute force search.
Not exactly. You can calulate Groebner basis with deglex ordering.
Then normal form gives you the word of the minimal length.
Victor Ufnarovski
From goetz at schmidt.nuigalway.ie Mon Mar 29 11:19:48 2004
From: goetz at schmidt.nuigalway.ie (Goetz Pfeiffer)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] length
In-Reply-To: <20040328050047.GA32201@realcool.org>
References: <20040328050047.GA32201@realcool.org>
Message-ID: <1080555588.22887.105.camel@schmidt.nuigalway.ie>
Dear Forum, dear marcus,
On Sun, 2004-03-28 at 06:00, marcus@thunder.realcool.org wrote:
> How can I compute the
> length of an element
> of a group, where by
> "length" I mean the minimum
> number of generators
> needed to write the element,
> assuming that I've fixed
> a generating set for the group.
> In particular, I need to do
> this for the symmetric group
> using generating set
> (1,2), (2,3), (3,4), ... (n-1,n)
the length of a permutation p with respect to
the generating set { (i, i+1) } is the number of pairs
i < j with i^p > j^p. It can for example be computed
by this function LengthPerm:
gap> LengthPerm:= p ->
> Sum([1..LargestMovedPoint(p)], j-> Number([1..j-1], i-> i^p > j^p));
function( p ) ... end
gap> LengthPerm((1,2,3,4,5));
4
gap> Collected(List(Elements(SymmetricGroup(4)), LengthPerm));
[ [ 0, 1 ], [ 1, 3 ], [ 2, 5 ], [ 3, 6 ], [ 4, 5 ], [ 5, 3 ], [ 6, 1 ] ]
In general, the computation of the length of a
group element is less straight forward.
Goetz Pfeiffer.
-------------------------------------------------------------------------
Goetz.Pfeiffer@NUIGalway.ie http://schmidt.nuigalway.ie/~goetz/
National University of Ireland, Galway. phone +353-91-512027 (x3591)
From stephen.lipp at edi-nola.com Tue Mar 30 14:49:25 2004
From: stephen.lipp at edi-nola.com (Stephen C. Lipp)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Cyclic permutation of five elements
Message-ID:
Problem 1: Given five elements find a cyclic set of transpositions which
will yield all permutations of these elements with respect to a given
permutation, namely (2,3,4,5).
Unfortunately, I am not speaking of permutations in the traditional
sense, but I am speaking of the indexing of the set. Hence, if I apply
the following transpositions
[<3,4>, <4,5>, <2,3>, <1,2>, <4,5>, <2,3>, <3,4>, <2,3>, <5,1>, <4,5>,
<1,2>, <3,4>, <2,3>, <3,4>, <1,2>, <5,1>, <1,2>, <4,5>, <5,1>, <4,5>,
<2,3>, <3,4>, <1,2>, <3,4>, <4,5>, <2,3>, <4,5>, <3,4>, <1,2>, <4,5>]
to the set [1,2,3,4,5] I get the cycle
[[1,2,4,3,5], [1,2,4,5,3], [1,4,2,5,3], [4,1,2,5,3], [4,1,2,3,5],
[4,2,1,3,5],
[4,2,3,1,5], [4,3,2,1,5], [5,3,2,1,4], [5,3,2,4,1], [3,5,2,4,1],
[3,5,4,2,1],
[3,4,5,2,1], [3,4,2,5,1], [4,3,2,5,1], [1,3,2,5,4], [3,1,2,5,4],
[3,1,2,4,5],
[5,1,2,4,3], [5,1,2,3,4], [5,2,1,3,4], [5,2,3,1,4], [2,5,3,1,4],
[2,5,1,3,4],
[2,5,1,4,3], [2,1,5,4,3], [2,1,5,3,4], [2,1,3,5,4], [1,2,3,5,4],
[1,2,3,4,5]]
The set of transpositions was obtained using an algorithm on a
spreadsheet with a random number generator.
This cycle contains all 5!/4 permutations of 5 elements where the last 4
elements are allowed to rotate. The terminology I am using would
indicate there exists an isomorphism between the index transpositions
and group permutations. Does such an isomorphism exist and, if so, what
is it?
Please forgive me if my use of the terminology is poor. It has been a
very long time since I made use of the terminology of group theory.
From kohl at mathematik.uni-stuttgart.de Tue Mar 30 17:38:03 2004
From: kohl at mathematik.uni-stuttgart.de (Stefan Kohl)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Cyclic permutation of five elements
References:
Message-ID: <4069A26B.A9C58B1@mathematik.uni-stuttgart.de>
Dear Stephen C. Lipp and Forum,
> Problem 1: Given five elements find a cyclic set of transpositions which
> will yield all permutations of these elements with respect to a given
> permutation, namely (2,3,4,5).
>
> Unfortunately, I am not speaking of permutations in the traditional
> sense, but I am speaking of the indexing of the set. Hence, if I apply
> the following transpositions
>
> [<3,4>, <4,5>, <2,3>, <1,2>, <4,5>, <2,3>, <3,4>, <2,3>, <5,1>, <4,5>,
> <1,2>, <3,4>, <2,3>, <3,4>, <1,2>, <5,1>, <1,2>, <4,5>, <5,1>, <4,5>,
> <2,3>, <3,4>, <1,2>, <3,4>, <4,5>, <2,3>, <4,5>, <3,4>, <1,2>, <4,5>]
>
> to the set [1,2,3,4,5] I get the cycle
>
> [[1,2,4,3,5], [1,2,4,5,3], [1,4,2,5,3], [4,1,2,5,3], [4,1,2,3,5],
> [4,2,1,3,5],
> [4,2,3,1,5], [4,3,2,1,5], [5,3,2,1,4], [5,3,2,4,1], [3,5,2,4,1],
> [3,5,4,2,1],
> [3,4,5,2,1], [3,4,2,5,1], [4,3,2,5,1], [1,3,2,5,4], [3,1,2,5,4],
> [3,1,2,4,5],
> [5,1,2,4,3], [5,1,2,3,4], [5,2,1,3,4], [5,2,3,1,4], [2,5,3,1,4],
> [2,5,1,3,4],
> [2,5,1,4,3], [2,1,5,4,3], [2,1,5,3,4], [2,1,3,5,4], [1,2,3,5,4],
> [1,2,3,4,5]]
>
> The set of transpositions was obtained using an algorithm on a
> spreadsheet with a random number generator.
>
> This cycle contains all 5!/4 permutations of 5 elements where the last 4
> elements are allowed to rotate. The terminology I am using would
> indicate there exists an isomorphism between the index transpositions
> and group permutations. Does such an isomorphism exist and, if so, what
> is it?
Let me try to guess what you want to say:
Apparently you describe a walk through the Cayley graph of the
symmetric group S_5 with the set of transpositions as generating set
which passes each element of the conjugacy class of the 4-cycles
exactly once.
The isomorphism you are looking for is probably just the
action isomorphism for the action of S_5 on the set {1,2,3,4,5}.
Please don't hesitate to ask in case I have misunderstood you or
if you have further questions.
Hope this helps,
Stefan Kohl
From scl at edi-nola.com Wed Mar 31 20:28:02 2004
From: scl at edi-nola.com (Stephen C. Lipp)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] FW: Cyclic permutation of five elements
Message-ID:
This is a re-posting of a message that had been "bounced."
-----Original Message-----
From: Stephen C. Lipp
Sent: Tuesday, March 30, 2004 7:49 AM
To: 'forum@gap-system.org'
Subject: Cyclic permutation of five elements
Problem 1: Given five elements find a cyclic set of transpositions which
will yield all permutations of these elements with respect to a given
permutation, namely (2,3,4,5).
Unfortunately, I am not speaking of permutations in the traditional
sense, but I am speaking of the indexing of the set. Hence, if I apply
the following transpositions
[<3,4>, <4,5>, <2,3>, <1,2>, <4,5>, <2,3>, <3,4>, <2,3>, <5,1>, <4,5>,
<1,2>, <3,4>, <2,3>, <3,4>, <1,2>, <5,1>, <1,2>, <4,5>, <5,1>, <4,5>,
<2,3>, <3,4>, <1,2>, <3,4>, <4,5>, <2,3>, <4,5>, <3,4>, <1,2>, <4,5>]
to the set [1,2,3,4,5] I get the cycle
[[1,2,4,3,5], [1,2,4,5,3], [1,4,2,5,3], [4,1,2,5,3], [4,1,2,3,5],
[4,2,1,3,5],
[4,2,3,1,5], [4,3,2,1,5], [5,3,2,1,4], [5,3,2,4,1], [3,5,2,4,1],
[3,5,4,2,1],
[3,4,5,2,1], [3,4,2,5,1], [4,3,2,5,1], [1,3,2,5,4], [3,1,2,5,4],
[3,1,2,4,5],
[5,1,2,4,3], [5,1,2,3,4], [5,2,1,3,4], [5,2,3,1,4], [2,5,3,1,4],
[2,5,1,3,4],
[2,5,1,4,3], [2,1,5,4,3], [2,1,5,3,4], [2,1,3,5,4], [1,2,3,5,4],
[1,2,3,4,5]]
The set of transpositions was obtained using an algorithm on a
spreadsheet with a random number generator.
This cycle contains all 5!/4 permutations of 5 elements where the last 4
elements are allowed to rotate. The terminology I am using would
indicate there exists an isomorphism between the index transpositions
and group permutations. Does such an isomorphism exist and, if so, what
is it?
Please forgive me if my use of the terminology is poor. It has been a
very long time since I made use of the terminology of group theory.
From reza_orfi at yahoo.com Wed Mar 31 21:54:32 2004
From: reza_orfi at yahoo.com (Reza Orfi)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] reza orfi from iran
Message-ID: <20040331205432.54248.qmail@web13009.mail.yahoo.com>
dear gap-forum
I need all normalsubgroups of this group
g=
And my computer can not list all
normalsubgroups of g .
please help me.
whit many thanks.
REZA ORFI
---------------------------------
Do you Yahoo!?
Yahoo! Finance Tax Center - File online. File on time.
From hulpke at math.colostate.edu Wed Mar 31 23:45:32 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] reza orfi from iran
In-Reply-To: <20040331205432.54248.qmail@web13009.mail.yahoo.com>
Message-ID: <200403312245.i2VMjW1i007557@schur.math.colostate.edu>
Dear Gap-Froum,
Reza Orfi wrote:
> I need all normalsubgroups of this group
> g=
> And my computer can not list all
> normalsubgroups of g .
Usually these types of calculations are easiest done in an isomorphic
permutation group:
gap> f:=FreeGroup("x","y");x:=f.1;y:=f.2;
x
y
gap> n:=[x^3,y^3,(x*y)^3*x/y*x*y/x*y*x/y];
[ x^3, y^3, x*y*x*y*x*y*x*y^-1*x*y*x^-1*y*x*y^-1 ]
gap> g:=f/n;
gap> hom:=IsomorphismPermGroup(g);;
gap> h:=Image(hom);
# now h is a permutation group with the same structure
gap> Size(h);
9000
gap> l:=NormalSubgroups(h);
[ Group(()), ,
,
, ,
,
,
]
gap> l:=List(l,i->PreImage(hom,i));
[ Group(), Group(),
Group(), Group(),
Group(), Group(),
Group(), Group() ]
Calculating concrete generators in the finitely presented group is a bit
more memory intensive:
gap> List(l,GeneratorsOfGroup);
[],
[y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1,
y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x],
[y*x*y^-1*x*y*x*y^-1*x,y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1,
y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1,y*x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y],
[x,y*x*y^-1,y^-1*x*y],
[y*x*y*x^-1*y*x^-1*y*x^-1*y*x*y*x^-1*y^-1*x^-1],
[y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1,y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x,
y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x,y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y*x],
[y*x*y*x^-1*y*x*y*x^-1,y*x*y^-1*x*y*x*y^-1*x,
y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1],
[x,y]]
Best wishes,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From wh at icparc.ic.ac.uk Thu Apr 1 00:37:29 2004
From: wh at icparc.ic.ac.uk (Warwick Harvey)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Finding a representative which moves fewest points
Message-ID: <20040401003727.A9726@tempest.icparc.ic.ac.uk>
Dear GAP Forum,
I am a relative novice when it comes to GAP and group theory, so please
excuse me if I've missed something obvious.
What I would like is a function like RepresentativeAction which returns a
representative that moves as few points as possible. Taking the example
from the manual:
gap> g:=Group((1,3,2),(2,4,3));;
gap> RepresentativeAction(g,1,3);
(1,3)(2,4)
I would like instead the element (1,3,2), since this only moves 3 points
rather than 4. I tried constructing cosets of the stabilizer of 1 and using
RepresentativeSmallest on the appropriate coset, but of course the notion of
smallest there is not what I want.
I have an algorithm in mind that I could use to construct a representative
of the form I desire, but don't want to re-invent the wheel if there's
already an easy way to do it.
Thanks for any tips.
Cheers,
Warwick
From hulpke at math.colostate.edu Thu Apr 1 19:37:52 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Re: Fp group (was: Orfi)
In-Reply-To: <20040331205432.54248.qmail@web13009.mail.yahoo.com>
Message-ID: <200404011837.i31IbqIM010518@schur.math.colostate.edu>
Thank you to all of you (so far: Eamonn O'Brien, Mike Newman, Derek Holt,
Werner Nickel) who pointed out that I misread a relation in the group as two
relators. The proper group is a bit bigger:
gap> f:=FreeGroup("x","y");x:=f.1;y:=f.2;
x
y
gap> n:=[x^3/y^3,(x*y)^3*x/y*x*y/x*y*x/y];
[ x^3*y^-3, x*y*x*y*x*y*x*y^-1*x*y*x^-1*y*x*y^-1 ]
gap> g:=f/n;
gap> hom:=IsomorphismPermGroup(g);;
gap> h:=Image(hom);;
gap> Size(h);
360000
IsomorphismPermGroup tries the action on the cosets of some cyclic
subgroups. In this case it fails and returns the regular representation.
gap> NrMovedPoints(h);
360000
Before continuing, lets therefore devote a bit of work to get the degree
smaller (the default GAP function for this would be
`SmallerDegreePErmutationRepresentation' but as it is very opportunistic and
does not try to spend too much time, it does not give an improvement):
Try to find some cyclic subgroup in the permutation group such that the
action on its cosets is faithful.
gap> r:=Random(h);;
gap> Order(r);
120
gap> r:=Random(h);;Order(r);
60
gap> u:=Subgroup(h,[r]);;
gap> v:=List(ConjugacyClassesSubgroups(u),Representative);;
gap> List(v,Size);
[ 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ]
gap> v:=Filtered(v,i->Size(Core(h,i))=1);
[ Group(()), ]
This is not good enough. Try again
gap> r:=Random(h);;Order(r);
30
gap> u:=Subgroup(h,[r]);;
gap> v:=List(ConjugacyClassesSubgroups(u),Representative);;
gap> v:=Filtered(v,i->Size(Core(h,i))=1);;
gap> List(v,Size);
[ 1, 2, 5, 10 ]
gap> u:=v[4];;
As the permutation action of h is regular, the action on the cosets of u is
given by action on the sets given by orbits of u:
gap> b:=Orbit(h,Set(Orbit(u,1)),OnSets);;
gap> h1:=ActionHomomorphism(h,b,OnSets);
We thus get a smaller degree permutation representation and proceed as
before:
gap> hom:=hom*h1;;
gap> h:=Image(hom);;
gap> n:=NormalSubgroups(h);;
gap> List(n,Size);
[ 1, 3, 2, 6, 4, 12, 8, 24, 5, 15, 10, 30, 20, 60, 40, 120, 125, 375, 250,
250, 750, 750, 500, 500, 1500, 1500, 1000, 1000, 3000, 3000, 250, 750, 500,
1500, 1000, 3000, 2000, 6000, 15000, 45000, 30000, 90000, 60000, 180000,
120000, 360000 ]
gap> np:=List(n,i->PreImage(hom,i));;
gap> Length(np);
46
Calculating generators for some of the smaller subgroups might become a bit
memory intensive. We therefore treat cyclic normal subgroups differently:
Instead of using `GeneratorsOfGroup' (which computes Schreier generators
using a coset table) we just take preimages for (permutation) generators
under the homomorphism:
gap> c:=Filtered([1..46],i->IsCyclic(n[i]));
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ]
gap> List(n{c},i->PreImagesRepresentative(hom,GeneratorOfCyclicGroup(i)));
[ , y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-1*y^
-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-2*y*x^-1*y*x^-2*y^-2*x^
-1*y^-1*x^-2, y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-1*y^
-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^
-1*x^-1, x^2*y*x*y*x*y*x*y^2*x^2*y^-1*x*y^-1*x^-1*y^-1*x*y*x*y*x^-1,
y^2*x*y^2*x*y^2*x^2*y*x^2*y^2*x^8*y^-1*x^-1*y^-1*x^-1*y*x*y,
x^2*y*x^2*y*x*y*x*y*x*y*x^2*y^-1*x^2*y*x*y*x^-1*y*x*y*x*y*x^-1*y,
x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^-1*y^-2*x^-2*y^-1*x^-1*y^-1*x^-1*y^-1*x^
-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-2*y^-1*x^-2,
y^-1*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y^-1*x^-1*y^-1*x^-2*y^-2*x^-2*y^-2*x^-2*y^
-2*x^-1*y^-2*x^-2*y^-1*x^-1*y^-1*x^-2, x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^
-1*y^-2*x^-5*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1*x^
-2*y^-1*x^-2, x*y*x^2*y^2*x*y^2*x^4*y^2*x*y^-1*x^-1*y^-1*x*y*x*y*x^-1,
x^12, x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^-1*y^-2*x^-1*y^-1*x^-1*y^-1*x^-2*y^
-2*x^-1*y^-2*x^-1*y^-1*x^-1*y^-1*x^-1*y^-1, x^-18,
x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x*y*x*y*x^-1*y*x^-1*y*x^-2*y^
-1*x^-1*y^-1*x^-2*y^-1*x^-2, y^-1*x^-1*y^-1*x*y*x*y*x^-11*y^-2*x^-2*y^
-1*x^-2*y^-2*x^-1*y^-2*x^-1*y^-2, y*x^2*y^2*x*y*x*y^2*x^2*y*x*y^2*x^5*y*x^
2*y^-1*x^-1*y^-1*x^-1*y*x*y ]
and treat the rest in the same way:
gap> List(np{Difference([1..46],c)},GeneratorsOfGroup);
[ [ y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1,
y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x,
y*x^-1*y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1 ],
[ y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x,
y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x ],
[ y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1,
y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1, y^2*x*y^-1*x*y*x*y^-1*x*y^-1 ],
[ x^-12, y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1,
y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ],
[ y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x,
y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x, x^-12 ],
[ y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x,
y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1 ],
[ x^-1*y*x*y^-1*x*y*x^-2*y^-1*x^-1, x^-1*y^-1*x*y*x*y^-1*x*y^-2*x^-1,
y*x^2*y^2*x^-1*y*x^-1*y^-1*x^-1, y^-1*x*y^-1*x*y*x*y^-1*x^-2*y^-1 ],
[ x^-6, y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1,
y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ],
[ x^-6, y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1,
y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x, y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x ]
, [ x^-1*y*x*y^-1*x*y*x^-2*y^-1*x^-1, x^-1*y*x^-1*y*x*y*x^-1*y^-2*x^-1,
x^-1*y^-1*x*y*x*y^-1*x*y^-2*x^-1 ],
[ x^-6, x^2*y*x^-1*y^-1*x^-1*y*x^-1*y^-1, x^2*y^-1*x^-1*y*x^-1*y^-1*x^-1*y,
x*y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x, y*x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y ],
[ x^3, y*x*y*x*y^-1*x*y^-1*x^-1*y^-1*x^-1*y*x^-1,
y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ],
[ x^3, y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1,
y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x, y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x,
y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x*y*x ],
[ x^-6, x^2*y*x*y*x^-1*y*x*y, x^2*y*x^-1*y^-1*x^-1*y*x^-1*y^-1,
x^2*y^-1*x*y^-1*x^-1*y^-1*x*y^-1 ],
[ x^-1*y*x*y^-1*x^-2*y^-2*x^-2*y^-1*x^-1,
x^-1*y^-1*x*y*x^-2*y^-1*x^-2*y^-2*x^-1, y*x^2*y^2*x^2*y*x^2*y^-1*x^-1,
y*x*y*x^-1*y*x^-1*y^-1*x^-1*y^-1*x*y^-1*x ],
[ y*x*y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1, y*x*y*x*y^-1*x^-1*y^-1*x^-1*y^-1*x,
y*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x, y*x^-1*y*x^-1*y*x^-1*y*x^-1*y*x^-1 ]
,
[ y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, y^-1*x^-1*y*x^
-1*y^-1*x^-1*y*x^-1, y^2*x*y^-1*x*y*x*y^-1*x*y^-1, x^-12 ],
[ y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x,
y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1, y*x^-1*y*x^-1*y*x^-1*y*x^-1*y*x^-1 ],
[ x^-6, y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1,
y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1, y^2*x*y^-1*x*y*x*y^-1*x*y^-1 ],
[ x^-6, y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x,
y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1 ],
[ x^3, y*x*y^-1*x*y*x*y^-1*x, y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1,
y^-1*x^-1*y*x^-1*y^-1*x^-1*y*x^-1, y*x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y ],
[ x^3, y*x*y*x^-1*y*x*y*x^-1, y*x*y^-1*x*y*x*y^-1*x,
y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x^-1 ],
[ y*x*y^-1*x^-1, y*x^-1*y^-1*x, y^-1*x*y*x^-1, y^-1*x^-1*y*x ],
[ y*x^-1, y^-1*x ], [ x^-4, y*x*y^-1*x^-1, y*x^-1*y^-1*x, y^-1*x*y*x^-1 ],
[ y*x^-1, y^-1*x, x^-4 ], [ x^-2, y*x*y^-1*x^-1, y^-1*x*y*x^-1 ],
[ x^-2, y*x^-1 ], [ x, y*x*y^-1, y^-1*x*y ], [ x, y ] ]
Best wishes,
Alexander Hulpke
From hulpke at math.colostate.edu Thu Apr 1 19:50:18 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Finding a representative which moves fewest points
In-Reply-To: <20040401003727.A9726@tempest.icparc.ic.ac.uk>
Message-ID: <200404011850.i31IoIMd010540@schur.math.colostate.edu>
Dear GAP Forum,
Warwick Harvey asked:
> What I would like is a function like RepresentativeAction which returns a
> representative that moves as few points as possible. Taking the example
> from the manual:
>
> gap> g:=Group((1,3,2),(2,4,3));;
> gap> RepresentativeAction(g,1,3);
> (1,3)(2,4)
>
> I would like instead the element (1,3,2), since this only moves 3 points
> rather than 4. I tried constructing cosets of the stabilizer of 1 and using
> RepresentativeSmallest on the appropriate coset, but of course the notion of
> smallest there is not what I want.
Basically you want to find an element x in the stabilizer of 3 so that r*x
fixes many points. If your group is of moderate degree, probvably the
following brute-force approach works:
gap> g:=Group((1,3,2),(2,4,3));;
gap> p1:=1;
gap> p2:=3;
gap> r:=RepresentativeAction(g,p1,p2);
(1,3)(2,4)
gap> s:=Stabilizer(g,p2);
Group([ (1,2,4) ])
gap> best:=r;
(1,3)(2,4)
gap> best:=r;bm:=NrMovedPoints(best);
(1,3)(2,4)
4
gap> for x in Enumerator(s) do
> a:=r*x;
> if NrMovedPoints(a) best:=a;bm:=NrMovedPoints(best);
> fi;
> od;
gap> best;
(1,3,2)
If your group gets bigger so that you do not want to run through all
elements in s, I would consider to map some points according to the orbits
of s.
Best wishes,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From wdj at USNA.Navy.Mil Thu Apr 1 16:21:48 2004
From: wdj at USNA.Navy.Mil (David Joyner)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Brauer characters
Message-ID: <406C338C.4040605@hermes.ewlab.usna.edu>
Hello GAP Forum:
Does GAP implement induction for Brauer characters?
- David
From scl at edi-nola.com Fri Apr 2 14:13:11 2004
From: scl at edi-nola.com (Stephen C. Lipp)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Cyclic permutation of five elements
Message-ID:
> Problem 1: Given five elements find a cyclic set of transpositions which
> will yield all permutations of these elements with respect to a given
> permutation, namely (2,3,4,5).
>
> Unfortunately, I am not speaking of permutations in the traditional
> sense, but I am speaking of the indexing of the set. Hence, if I apply
> the following transpositions
>
> [<3,4>, <4,5>, <2,3>, <1,2>, <4,5>, <2,3>, <3,4>, <2,3>, <5,1>, <4,5>,
> <1,2>, <3,4>, <2,3>, <3,4>, <1,2>, <5,1>, <1,2>, <4,5>, <5,1>, <4,5>,
> <2,3>, <3,4>, <1,2>, <3,4>, <4,5>, <2,3>, <4,5>, <3,4>, <1,2>, <4,5>]
>
> to the set [1,2,3,4,5] I get the cycle
>
> [[1,2,4,3,5], [1,2,4,5,3], [1,4,2,5,3], [4,1,2,5,3], [4,1,2,3,5],
> [4,2,1,3,5],
> [4,2,3,1,5], [4,3,2,1,5], [5,3,2,1,4], [5,3,2,4,1], [3,5,2,4,1],
> [3,5,4,2,1],
> [3,4,5,2,1], [3,4,2,5,1], [4,3,2,5,1], [1,3,2,5,4], [3,1,2,5,4],
> [3,1,2,4,5],
> [5,1,2,4,3], [5,1,2,3,4], [5,2,1,3,4], [5,2,3,1,4], [2,5,3,1,4],
> [2,5,1,3,4],
> [2,5,1,4,3], [2,1,5,4,3], [2,1,5,3,4], [2,1,3,5,4], [1,2,3,5,4],
> [1,2,3,4,5]]
>
> The set of transpositions was obtained using an algorithm on a
> spreadsheet with a random number generator.
>
> This cycle contains all 5!/4 permutations of 5 elements where the last 4
> elements are allowed to rotate. The terminology I am using would
> indicate there exists an isomorphism between the index transpositions
> and group permutations. Does such an isomorphism exist and, if so, what
> is it?
Let me try to guess what you want to say:
Apparently you describe a walk through the Cayley graph of the
symmetric group S_5 with the set of transpositions as generating set
which passes each element of the conjugacy class of the 4-cycles
exactly once.
The isomorphism you are looking for is probably just the
action isomorphism for the action of S_5 on the set {1,2,3,4,5}.
Please don't hesitate to ask in case I have misunderstood you or
if you have further questions.
Hope this helps,
Stefan Kohl
------------------------------------------------------------------------
So I am looking for a cyclic walk through the Cayley table of 120 elements where the equivalence classes are with respect to rotation on the last 4 elements of the set. Hence there are 30 steps taken to cover all the classes. The obvious question that arises is,
How does one find a "walk" through this set?
As pointed out in the initial E-mail, the walk was found using an algorithm (basically a depth-first search) on a spreadsheet with a random number generator. Now suppose the set is larger (the Cayley table is 5040 elements where the equivalence classes are with respect to a rotation of order 3). Hence there are 1680 steps taken to cover all the partitions of the set. Is there a more efficient algorithm than a depth-first search?
The other question that has not been addressed is existence. Does such a walk exist? If, for example, I try to walk through S_3 where the equivalence class is with respect to transposition of the first two elements of the set, such a transposition walk does not exist.
Stephen C. Lipp
From wdj at madeline.usna.edu Sat Apr 3 20:59:10 2004
From: wdj at madeline.usna.edu (David Joyner)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] guava 1.9
Message-ID: <406F178E.1010001@gwweb.usna.edu>
Hello GAP Forum:
This is to announce that the next version of GAP's error-correcting
codes package GUAVA, version 1.9, is ready. Many thanks to Frank
Luebeck for help with this. I hope the permission problems Frank
discovered are corrected.
From the CHANGES file:
Version 1.9 has:
o Faster MinimumDistance algorithm (joint with Aron Foster, a student).
o MinimumDistanceLeon algorithm (joint with Aron Foster).
o Faster PutStandard form algorithm (with GAP's Frank Luebeck).
o New PermutationGroup command (for possibly non-binary codes).
o New PermutationDecode command.
See the manual on the web page for more information and downloading:
http://cadigweb.ew.usna.edu/~wdj/gap/GUAVA/
Pleas email me if you experience any problems.
- David Joyner
From dima at thi.informatik.uni-frankfurt.de Tue Apr 6 09:56:03 2004
From: dima at thi.informatik.uni-frankfurt.de (Dmitrii Pasechnik)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] decomposition formulae for C-representations
Message-ID: <20040406085603.GA7964@thi21.thi.informatik.uni-frankfurt.de>
Dear Forum,
are the formulae that give the decomposition of a C-represenation p
of a finite group G into direct sums of irreducibles implemented in GAP?
(perhaps somewhere within character theory machinery I guess)
I mean the standard ones given in e.g. Serre's "Linear Representations
of Finite Groups", Sect. 2.6 and 2.7.
For instance to obtain the subrepresentation of p (a direct sum of
irreducible representations with the same character chi) of dimension
n_chi, corresponding to the irrducible character chi, one uses the projection
n_chi/|G| sum_{g in G} chi^*(g)p(g)
(Thm. 8 in Sect. 2.6 of the Serre's book)
Certainly, this is only feasible for groups of relatively small order
to use these formulae directly, but in our case the groups
are of order <10^4.
thanks
Dmitrii
From carcher at ulb.ac.be Tue Apr 6 13:24:36 2004
From: carcher at ulb.ac.be (carcher@ulb.ac.be)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] New features for the Polycyclic package ;
Message-ID: <200404061224.OAA26217@web1.ulb.ac.be>
I have some question about the very nice Polycyclic Package of Bettina and Werner.
First of all, thank you for the package.
Here are my questions
1) how are cocycle components ordered for Pcp groups ?
For finite pc group there is a line in file
in /lib/twocohom.gi
## The tail of a conjugate i^j (i>j) or a power i^p (i=j) is stored at
## posiition (i^2-i)/2+j
that gives the solution.
Unfortunately i haven't found such a line in the code of the polycyclic package.
2)
I would like to compute the second cohomology groups Z2(G,A) and B2(G,A) of an arbitrary finitely generated
abelian group A. In the gap library, this is only possible if A is elementary abelian and
G is polycyclic. Are there any plan to do it for arbitrary A and G polycyclic ?
And for G a non polycyclic permutation group ?
Derek Holt has implemented in Magma a method for A arbitrary and i think that
further developments of your Polycyclic package is the solution to implement it in GAP.
The idea is to write the module action on A by integer matrices and to add linear equations
to the linear system needed to compute the cocycle. This new equations specify that some
coefficients of the system have to be interpreted modulo an integer.
i have tried to do the job by myself first by modifyng the equations of the linear system.
In attachement you can find a modify version of the function TwoCocyclesCR.
--> see attachement TwoCocyclesCRbis:=function( A, invarlist )
3) Is there some plan to provide automorphisms group of Pcp group ?
4) Another nice posibility of the polycyclic package is to use non prime pcgs.
But, if for a given pcp group G one wants to construct G one a non prime pcgs there is no function
to do so without refining it into a prime pcgs.
A nice application of non prime pcgs is the ability to reduce the number of unknowns
in the linear system to determine cocycle
Thank you very much for your help
Claude
-------------- next part --------------
#############################################################################
##
#F TwoCocyclesCRbis( A, invarlist )
### Twococyles for a finitely generated abelian group,
## described as a product of the cyclic group invarlist[i]
##InstallGlobalFunction( TwoCocyclesCRbis, function( A , invarlist )
TwoCocyclesCRbis:=function( A, invarlist )
local C, n, e, id, l, gn, gp, gi, eq, pairs, i, j, k, w1, w2, d, sys, h,
### new variables for the new code (arbitrary finitely generated abelian group)
m,standardvect,fullkernel,ll;
# set up system of length d
n := Length( A.mats );
e := RelativeOrdersOfPcp( A.factor );
l := Length( A.enumrels );
d := A.dim;
sys := CRSystem( d, l, A.char );
# set up for equations
id := IdentityMat(n);
gn := List( id, x -> rec( word := x, tail := [] ) );
# precompute (ij) for i > j
pairs := List( [1..n], x -> [] );
for i in [1..n] do
if e[i] > 0 then
h := rec( word := (e[i] - 1) * id[i], tail := [] );
pairs[i][i] := CollectedTwoCR( A, h, gn[i] );
fi;
for j in [1..i-1] do
pairs[i][j] := CollectedTwoCR( A, gn[i], gn[j] );
od;
od;
# consistency 1: k(ji) = (kj)i
for i in [ n, n-1 .. 1 ] do
for j in [ n, n-1 .. i+1 ] do
for k in [ n, n-1 .. j+1 ] do
w1 := CollectedTwoCR( A, gn[k], pairs[j][i] );
w2 := CollectedTwoCR( A, pairs[k][j], gn[i] );
if w1.word <> w2.word then
Error( "k(ji) <> (kj)i" );
else
AddEquationsCR( sys, w1.tail, w2.tail, true );
fi;
od;
od;
od;
# consistency 2: j^(p-1) (ji) = j^p i
for i in [n,n-1..1] do
for j in [n,n-1..i+1] do
if e[j] > 0 then
h := rec( word := (e[j] - 1) * id[j], tail := [] );
w1 := CollectedTwoCR( A, h, pairs[j][i]);
w2 := CollectedTwoCR( A, pairs[j][j], gn[i]);
if w1.word <> w2.word then
Error( "j^(p-1) (ji) <> j^p i" );
else
AddEquationsCR( sys, w1.tail, w2.tail, true );
fi;
fi;
od;
od;
# consistency 3: k (i i^(p-1)) = (ki) i^p-1
for i in [n,n-1..1] do
if e[i] > 0 then
h := rec( word := (e[i] - 1) * id[i], tail := [] );
l := CollectedTwoCR( A, gn[i], h );
for k in [n,n-1..i+1] do
w1 := CollectedTwoCR( A, gn[k], l );
w2 := CollectedTwoCR( A, pairs[k][i], h );
if w1.word <> w2.word then
Error( "k i^p <> (ki) i^(p-1)" );
else
AddEquationsCR( sys, w1.tail, w2.tail, true );
fi;
od;
fi;
od;
# consistency 4: (i i^(p-1)) i = i (i^(p-1) i)
for i in [ n, n-1 .. 1 ] do
if e[i] > 0 then
h := rec( word := (e[i] - 1) * id[i], tail := [] );
l := CollectedTwoCR( A, gn[i], h );
w1 := CollectedTwoCR( A, l, gn[i] );
w2 := CollectedTwoCR( A, gn[i], pairs[i][i] );
if w1.word <> w2.word then
Error( "i i^p-1 <> i^p" );
else
AddEquationsCR( sys, w1.tail, w2.tail, true );
fi;
fi;
od;
# consistency 5: j = (j -i) i
gi := List( id, x -> rec( word := -x, tail := [] ) );
for i in [n,n-1..1] do
for j in [n,n-1..i+1] do
#if e[i] = 0 then
w1 := CollectedTwoCR( A, gn[j], gi[i] );
w2 := CollectedTwoCR( A, w1, gn[i] );
if w2.word <> id[j] then
Error( "j <> (j -i) i" );
else
AddEquationsCR( sys, w2.tail, [], true );
fi;
#fi;
od;
od;
# consistency 6: i = -j (j i)
for i in [n,n-1..1] do
for j in [n,n-1..i+1] do
if e[j] = 0 then
w1 := CollectedTwoCR( A, gi[j], pairs[j][i] );
if w1.word <> id[i] then
Error( "i <> -j (j i)" );
else
AddEquationsCR( sys, w1.tail, [], true );
fi;
fi;
od;
od;
# consistency 7: -i = -j (j -i)
for i in [n,n-1..1] do
for j in [n,n-1..i+1] do
if e[i] = 0 and e[j] = 0 then
w1 := CollectedTwoCR( A, gn[j], gi[i] );
w1 := CollectedTwoCR( A, gi[j], w1 );
if w1.word <> -id[i] then
Error( "-i <> -j (j -i)" );
else
AddEquationsCR( sys, w1.tail, [], true );
fi;
fi;
od;
od;
# add a check ((j ^ i) ^-i ) = j
for i in [1..n] do
for j in [1..i-1] do
w1 := CollectedTwoCR( A, gi[j], pairs[i][j] );
w1 := CollectedTwoCR( A, gn[j], w1 );
w1 := CollectedTwoCR( A, w1, gi[j] );
if w1.word <> id[i] then
Error("in rel check ");
elif not IsZeroTail( w2.tail ) then
# Error("relations bug");
AddEquationsCR( sys, w1.tail, [], true );
fi;
od;
od;
###########################################
######### new code for arbitrary abelian group
m:=Length(sys.base)/d;
# Now, we add d*m new unknowns y[k] as follows :
# since equation k=j*d+i evaluates to 0 (mod invarlist[i]), a multiple of invarlist[i],
# we add the multiple y[k]*invarlist[i] to equation[k]
for i in [1..d] do
for j in [0..m-1] do
standardvect:=List([1..d*m],x->0);
standardvect[j*d+i]:=invarlist[i];
Append( sys.base[j*d+i],standardvect);
od;
od;
fullkernel:=KernelCR( A, sys ).basis;
### Now, we get rid off the d*m auxilliary unknowns we added
### we want the projection of the null space NS on the l*d original coordinates
## If the solutions in {B} form a basis for NS then proj({B}) generates proj(NS).
## Moreover the component [j*d+i] of a vector in proj({B}) may be reduced mod invarlist[i]
## improvement ? : the coefficients of fullkernel can be very large so we should have a
## way to reduce them during the calculation of KernelCR( A, sys ).basis;
## if we want to preserve the type of fullkernel
ll:=Length(A.enumrels);
# l has changed, why ? so we rename it
for k in [1..Length(fullkernel)] do
fullkernel[k]:=fullkernel[k]{[1..ll*d]};
for i in [1..d] do
for j in [0..ll-1] do
fullkernel[k][j*d+i]:=fullkernel[k][j*d+i] mod invarlist[i];
od;
od;
od;
# and return solution
return Set(fullkernel);
## after the modulo reduction, many zero vectors appear
end ;
#############################################################################
From jjoao at netcabo.pt Mon Apr 5 22:34:19 2004
From: jjoao at netcabo.pt (Jose Joao Morais)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] InstallCharReadHookFunc
Message-ID: <1081200746.5806.3.camel@a81-84-193-207.netcabo.pt>
Dear GAP Forum,
I have the following code:
gap> d := Directory("/home/josejoao/Projects/project2/src");;
gap> f := Filename(d, "gapmenu");;
gap> gapmenustream := InputOutputLocalProcess(d,f,[]);;
gap> func := function()
> Print(ReadAll(gapmenustream));
> end;;
gap> InstallCharReadHookFunc( gapmenustream, "r", func );
But as soon as there is somethig ready to be read from the stream, I
get the following error:
gap> Function: number of arguments must be 0 (not 1)
not in any function
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can replace the argument list via 'return ;' to
continue
Can someone tell me what is wrong in this?
Thank you,
Jose Morais
From wdj at USNA.Navy.Mil Wed Apr 7 15:54:35 2004
From: wdj at USNA.Navy.Mil (David Joyner)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] decomposition formulae for C-representations
In-Reply-To: <20040406085603.GA7964@thi21.thi.informatik.uni-frankfurt.de>
References: <20040406085603.GA7964@thi21.thi.informatik.uni-frankfurt.de>
Message-ID: <4074162B.3060406@hermes.ewlab.usna.edu>
Dmitrii Pasechnik wrote:
>Dear Forum,
>
>are the formulae that give the decomposition of a C-represenation p
>of a finite group G into direct sums of irreducibles implemented in GAP?
>(perhaps somewhere within character theory machinery I guess)
>
>I mean the standard ones given in e.g. Serre's "Linear Representations
>of Finite Groups", Sect. 2.6 and 2.7.
>For instance to obtain the subrepresentation of p (a direct sum of
>irreducible representations with the same character chi) of dimension
>n_chi, corresponding to the irrducible character chi, one uses the projection
> n_chi/|G| sum_{g in G} chi^*(g)p(g)
>(Thm. 8 in Sect. 2.6 of the Serre's book)
>
>Certainly, this is only feasible for groups of relatively small order
>to use these formulae directly, but in our case the groups
>are of order <10^4.
>
>thanks
>Dmitrii
>
>_______________________________________________
>Forum mailing list
>Forum@mail.gap-system.org
>http://mail.gap-system.org/mailman/listinfo/forum
>
>
How is your repn p entered? For example,
A5:=AlternatingGroup(5);
A5_repns:=Irr(A5);
C:=Centralizer(A5,(1,2)(3,4));
C_repns:=Irr(C);
ind:=InducedClassFunction(C_repns[1],A5);
m:=List(A5_repns,x->ScalarProduct(ind,x));
returns the multiplicities occuring in an
induced repn.
If p is entered as a class function, I'm not sure,
but I'd like to know too!
From scl at edi-nola.com Wed Apr 7 22:07:58 2004
From: scl at edi-nola.com (Stephen C. Lipp)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Cyclic permutation of five elements
Message-ID:
So I am looking for a cyclic walk through the Cayley table of 120
elements
where the equivalence classes are with respect to rotation on the last
4 elements of the set. Hence there are 30 steps taken to cover all the
classes. The obvious question that arises is,
How does one find a "walk" through this set?
As pointed out in the initial E-mail, the walk was found using an
algorithm
(basically a depth-first search) on a spreadsheet with a random number
generator. Now suppose the set is larger (the Cayley table is 5040
elements
where the equivalence classes are with respect to a rotation of order
3).
Hence there are 1680 steps taken to cover all the partitions of the set.
Is
there a more efficient algorithm than a depth-first search?
The other question that has not been addressed is existence. Does such
a walk
exist? If, for example, I try to walk through S_3 where the equivalence
class
is transposition of the first two elements of the set, such a
transposition
walk does not exist. There is no way to walk from [1, 2, 3] through the
other
two equivalence classes and arrive back at [1, 2, 3] in three steps.
Stephen C. Lipp
From thomas.breuer at math.rwth-aachen.de Thu Apr 8 08:39:37 2004
From: thomas.breuer at math.rwth-aachen.de (Thomas Breuer)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Re: decomposition formulae for C-representations
Message-ID:
Dear GAP Forum,
Dima Pasechnik asked
> are the formulae that give the decomposition of a C-represenation p
> of a finite group G into direct sums of irreducibles implemented in GAP?
> (perhaps somewhere within character theory machinery I guess)
>
> I mean the standard ones given in e.g. Serre's "Linear Representations
> of Finite Groups", Sect. 2.6 and 2.7.
> [...]
> Certainly, this is only feasible for groups of relatively small order
> to use these formulae directly, but in our case the groups
> are of order <10^4.
I am not aware of a GAP implementation for that.
One possibility for groups of this small order would certainly be
to compute the character of the given representation,
to decompose it into irreducibles,
to compute all irreducible representations of the group,
and to use their characters for deciding which ones occur as summands
of the given representation.
Of course this can be viewed as an ugly attempt because it does not
really decompose the given data.
But computing the irreducible representations of small groups is not hard,
and for the case of abelian by supersolvable groups one gets them in the
nice form of monomial representations.
The question is whether this suffices or whether you need the explicit
base change that transforms the given matrices into block diagonal form.
(And of course another question is whether it would be possible to avoid
computations with representations at all.)
All the best,
Thomas
From hulpke at math.colostate.edu Fri Apr 9 03:45:46 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] decomposition formulae for C-representations
Message-ID: <200404090245.i392jknK010764@schur.math.colostate.edu>
Dear Gap-Forum,
(Somehow my original reply only went to Dima Pasechnik and not to the list.
Thus a bit belatedly:)
Dima Pasechnik wrote:
> are the formulae that give the decomposition of a C-represenation p
> of a finite group G into direct sums of irreducibles implemented in GAP?
To my knowledge they are not immediately implemented, but it is relatively
easyly done (I leave out the GAP output as it gets quite long):
# construct some group and a matrix representation (this is your input)
g:=TransitiveGroup(12,150);
mats:=List(GeneratorsOfGroup(g),i->PermutationMat(i,12,1));
# matrix rep.
hom:=GroupHomomorphismByImages(g,Group(mats),GeneratorsOfGroup(g),mats);
# get character table and corresponding character
c:=CharacterTable(g);
char:=ClassFunction(c,List(ConjugacyClasses(c),
i->TraceMat(Image(hom,Representative(i)))));
# calculate decomposition
MatScalarProducts(Irr(c),[char]);
# In the example character 9 occurs. find the submodule
x:=Irr(c)[9];
l:=Length(ConjugacyClasses(c));
# the projectuion matrix according to the formula you gave (I sum up the
# elements according to conjugacy classes:
proj:=x[1]/Size(g)*Sum([1..l],i->GaloisCyc(x[i],-1)
*Sum(Elements(ConjugacyClasses(c)[i]),j->Image(hom,j)));
# its rank (the dimension of the module) and a basis
RankMat(proj);
v:=BaseMat(proj);
# for example the induced action on the submodule.
induc:=List(mats,i->List(v,j->SolutionMat(v,j*i)));
I hope this helps,
Alexander
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
From vdabbagh at math.carleton.ca Sun Apr 11 17:50:56 2004
From: vdabbagh at math.carleton.ca (Vahid Dabbaghian-Abdoly)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] decomposition formulae for C-representations
In-Reply-To: <20040406085603.GA7964@thi21.thi.informatik.uni-frankfurt.de>
Message-ID:
Dear Dima and Dear GAP forum.
I have developed a GAP share package "REPSN" to construct
representations of finite groups. You can use this package to construct
representations affording the given character. If you know
constituents then using this package you can compute
representations corresponding to these constituents to find a
decomposition of the given representation.
If you are interested please let me know then I can send you a prereleased
version of that.
Regards, Vahid Dabbaghian-Abdoly
http://math.carleton.ca/~vdabbagh
Tel: (613) 520-2600 ext. 8789
School of Mathematics and Statistics
Room 4356, Herzberg Building
1125 Colonel By Drive, Carleton University
Ottawa, Ontario, CANADA K1S 5B6
From vvk at csu.ru Tue Apr 13 04:25:37 2004
From: vvk at csu.ru (vvk@csu.ru)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Re: Protected Mail Delivery
Message-ID: <200404130324.i3D3Of1C002236@gap-system.org>
Protected message is available.
++++ Attachment: No Virus found
++++ Norton AntiVirus - www.symantec.de
From e.obrien at auckland.ac.nz Tue Apr 13 08:49:03 2004
From: e.obrien at auckland.ac.nz (e.obrien@auckland.ac.nz)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Re: Delivery Protection
Message-ID: <200404130748.i3D7lw1C006965@gap-system.org>
Protected message is available.
From sal at dcs.st-and.ac.uk Tue Apr 13 10:33:30 2004
From: sal at dcs.st-and.ac.uk (Steve Linton)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Two spurious messages
Message-ID: <20040413103330.1fcbaec3@caolila.dcs.st-and.ac.uk>
Dear GAP Forum,
Two messages were sent out to the forum today, apparently from
e.obrien@auckland.ac.nz and vvk@csu.ru
These were in fact sent by a virus-infected computer apperantly in Russia (as
you can see by a close examination of the headers).
Any non-text attachments on forum messages are removed by mailman
automatically, so these messages did not carry viruses.
We will work on improving our defences against such mails. In the mean time,
please just ignore them.
Steve
--
Steve Linton School of Computer Science &
Centre for Interdisciplinary Research in Computational Algebra
University of St Andrews Tel +44 (1334) 463269
http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278
From sal at dcs.st-and.ac.uk Tue Apr 13 18:18:53 2004
From: sal at dcs.st-and.ac.uk (Steve Linton)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Re: InstallCharReadHookFunc
Message-ID: <20040413181853.191c558c@caolila.dcs.st-and.ac.uk>
Dear GAP Forum,
Jose Morais asked:
> gap> func := function()
> > Print(ReadAll(gapmenustream));
> > end;;
> gap> InstallCharReadHookFunc( gapmenustream, "r", func );
>
> But as soon as there is somethig ready to be read from the stream, I
> get the following error:
>
> gap> Function: number of arguments must be 0 (not 1)
> not in any function
> Entering break read-eval-print loop ...
> you can 'quit;' to quit to outer loop, or
> you can replace the argument list via 'return ;' to
> continue
>
>
> Can someone tell me what is wrong in this?
The problem here is that the function supplied to InstallCharReadHookFunc must
take one argument (which it can ignore). The manual mentions this, in passing:
Note that handler functions must not return anything and get one integer
^^^^^^^^^^^^^^^^^
argument, which refers to an index in one of the following arrays (according to
^^^^^^^^
whether the function was installed for input, output or exceptions on the
stream).
Your message is produced when your function func() which takes no arguments is
called by GAP with one argument.
Steve
--
Steve Linton School of Computer Science &
Centre for Interdisciplinary Research in Computational Algebra
University of St Andrews Tel +44 (1334) 463269
http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278
From beick at tu-bs.de Thu Apr 15 13:59:52 2004
From: beick at tu-bs.de (Bettina Eick)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] New features for the Polycyclic package ;
In-Reply-To: <200404061224.OAA26217@web1.ulb.ac.be>
Message-ID:
Dear Claude, dear Forum-members,
> 1) how are cocycle components ordered for Pcp groups ?
Let G be a pcp-group and let M = Z^d be a G-module. Suppose that G has l
relators in its polycyclic presentation. Then the cocycles are returned
as vectors of length l*d. Every vector is the concatenation of the l tails
to the polycyclic relations of G. The relators of G are sorted for this
purpose and the sorting is recorded in the cohomology record.
An example:
the infinite Dihedralgroup acting on Z as trivial module.
gap> G := DihedralPcpGroup(0);;
gap> mats := [IdentityMat(1), IdentityMat(1)];;
gap> CR := CRRecordByMats(G,mats);;
gap> CR.enumrels;
[ [ 1, 1 ], [ 2, 1 ], [ 2, 3 ] ]
gap> TwoCohomologyCR(CR).gcc;
[ [ 1, 0, 0 ], [ 0, 1, 1 ] ]
CR.enumrels tells you that there are three relations and they are sorted:
[1,1] corresponds to the power relation g1^2
[2,1] corresponds to the conjugate relation g2^g1
[2,3] corresponds to the conjugate relation with the inverse g2^(g1^-1)
Thus the cocycles are returned as vectors of length 3.
> 2)
> I would like to compute the second cohomology groups Z2(G,A) and B2(G,A)
> of an arbitrary finitely generated abelian group A. In the gap library,
> this is only possible if A is elementary abelian and G is polycyclic.
There is also Derek's Cohomolo Package for arbitrary finite groups G. If
you want to do a similar computation for finite abelian groups A which are
not elementary abelian, then you can use a G-invariant series through A
with elementary abelian factors and do induction along such a series.
The case of an elementary or free abelian module A and a polycyclic factor
G is covered in the Polycyclic package. Again, using induction along a series
you could use this to deal with finitely generated abelian groups A.
> 3) Is there some plan to provide automorphisms group of Pcp group ?
For a finite pcp-group you can translate the automorphism group from the
automorphism group of its corresponding pc-group.
> 4) Another nice posibility of the polycyclic package is to use non prime
> pcgs. But, if for a given pcp group G one wants to construct G one a non
> prime pcgs there is no function to do so without refining it into a prime
> pcgs.
I do not understand this comment. Surely, you can define a pcp-group in
GAP on a non-prime pcgs:
gap> G := DihedralPcpGroup(20);
Pcp-group with orders [ 2, 10 ]
Hope this helps,
Bettina
From hulpke at math.colostate.edu Thu Apr 15 20:49:35 2004
From: hulpke at math.colostate.edu (Alexander Hulpke)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Release Announcement: GAP 4.4
Message-ID: <200404151949.i3FJnaSL012676@schur.math.colostate.edu>
Dear Gap-Forum,
GAP 4.4 is available! It contains a variety of new features, improved
algorithms and new programming tools. A detailed outline is included
below.
We recommend all GAP 4 users to upgrade to GAP 4.4 and we wish you fun
and success in using GAP.
You can download the new version of GAP from
http://www.gap-system.org
The GAP group
#############################################################################
New Mathematical Features
-------------------------
* New Algorithms and Functions in GAP
- Groebner Bases:
Buchberger's algorithm to compute Groebner Bases has been implemented
in GAP. (By A. Hulpke)
For large scale Groebner Basis computations there also is an interface
to the Singular system available in the 'Singular' Package.
(By M. Costantini and W. de Graaf)
- Algebraic Field Extension:
New methods for factorizing polynomials over algebraic extensions of
the rationals have been implemented in GAP. (By A. Hulpke)
For more functionality to compute with algebraic number fields there
is an interface to the Kant system available in the 'Alnuth' Package.
(By B. Assmann and B. Eick)
- Galois Groups:
A method for computing the Galois group of a rational polynomial has
been implemented in GAP. (By A. Hulpke)
- Finite Groups:
A new operation and a new method to compute the minimal normal subgroups
of a finite group and a method to determine the socle of a finite group
has been installed. (By B. Hoefling)
- Permutation Groups:
A fast method for recognizing whether a permutation group is symmetric
or alternating in its natural representation is available now.
(By A. Seress)
- Brauer Tables:
The algorithm for 'BrauerCharacterValue' has been extended to the case
where the splitting field is not supported in GAP. (By T. Breuer)
Brauer tables of direct products can now be constructed from the
known Brauer tables of the direct factors. (By T. Breuer)
- Vector spaces:
Basic support for vector spaces of rational functions and of uea
elements is available now in GAP. (By T. Breuer and W. de Graaf)
- Integer matrices:
Various new functions for computations with integer matrices are
available, such as methods for computing normal forms of integer
matrices as well as nullspaces or solutions systems of equations.
(By W. Nickel and F. Gaehler)
- Meataxe:
It is now possible to compute invariant forms and orthogonal signs of
modules. (By D. Holt and J. Thackray)
#############################################################################
* New Packages for GAP
The following new Packages have been accepted.
- LAGUNA: Computing with Lie Algebras and Units of Group Algebras.
By V. Bovdi, A. Konovalov, R. Rossmanith, C. Schneider.
- NQ: The ANU Nilpotent Quotient Algorithm.
By W. Nickel.
- KBMAG: Knuth-Bendix for Monoids and Groups.
By D. Holt.
- QuaGroup: Computing with Quantized Enveloping Algebras.
By W. de Graaf.
- AlNuTh: Algebraic Number Theory and an Interface to the Kant System.
By B. Assmann and B. Eick
- Polycyclic: Computation with Polycyclic Groups.
By B. Eick and W. Nickel
- Sonata: Construction and analysis of finite nearrings.
By E. Aichinger, F. Binder, J. Ecker, P. Mayr, C. Noebauer
#############################################################################
* Performance Enhancements
- Character Theory:
The computation of irreducible representations and irreducible
characters using the Baum-Clausen algorithm and the implementation of
the Dixon-Schneider algorithm have been speeded up. The algorithm for
'PossibleClassFusions' has been changed: the efficiency has been
improved and a new criterion is used. The algorithm for
'PossibleFusionsCharTableTom' has been speeded up. The method for
'PrimeBlocks' has been improved following a suggestion of H. Pahlings.
- Symmetric Groups
New improved methods for normalizer and subgroup conjugation in Sn have
been installed and new improved methods for IsNaturalSn/An have been
implemented. These improve the available methods when groups of large
degrees are given.
- Permutation Groups:
The partition split method used in the permutation backtrack is now
in the kernel. Transversal computations in large permutation groups
are improved. The decomposition of a permutation as a word in the
generators now produces substantially shorter words: for example, the
words have lengths about 100 for the Rubics Cube group.
- Matrix Groups:
The membership test in SP and SU has been improved using the invariant
forms underlying these groups.
- Finite groups:
An improvement for the cyclic extension method has been implemented.
- Matrices:
A better method for MinimalPolynomial for finite field matrices has been
implemented.
- Polynomials:
The display has changed and the arithmetic of multivariate polynomials
has been improved.
- LogMod:
Uses now Pollard's rho method combined with the Pohlig/Hellmann approach.
(By Sean Gage)
- Lists:
Various functions for sets and lists have been improved following
suggestions of L. Teirlinck. These include: Sort, Sortex, SortParallel,
SortingPerm, NrArrangements.
- Finite Dimensional Algebras:
The methods for 'StructureConstantsTable' and 'GapInputSCTable' have
been improved in the case of a known (anti-) symmetry following a
suggestion of M. Costantini.
Unless otherwise stated, the improvements listed in this Section have been
implemented by T. Breuer and A. Hulpke.
#############################################################################
* Technical changes in GAP and new programming tools
- IsSimple: Returns false now for the trivial group.
- PrimeBlocks: The output format has changed.
- Division Rings: These are implemented as 'IsRingWithOne' now.
- DirectSumOfAlgebras: Pth power maps are compatible with the input now.
- EnumeratorByFunctions: A new tool to create enumerators.
- IteratorByFunctions: A new tool to create iterators.
#############################################################################
* Bug Fixes
It remains to mention that GAP 4.4 includes fixes for all bugs which
had been reported before the deadline for the release.
#############################################################################
New Programming and User Features
---------------------------------
- Workspaces: The 2GB limit has been removed and version numbers have
been introduced. (By S. Linton and B. Hoefling)
- Types: The limit on the total number of types created in a session
has been removed. (By S. Linton)
- Packages: There is a new mechanism for loading packages available.
Packages need a file PackageInfo.g now. (By T. Breuer and
F. Luebeck)
#############################################################################
Upwards Compatibility
---------------------
The mechanism for the loading of Packages has changed. Packages require
a file PackageInfo.g now. These new PackageInfo.g files are available
for all accepted and deposited Packages within GAP 4.4.
Apart from the Package loading, there are only some other very minor
changes (e.g. the trivial group is not a simple group in GAP any longer)
which are not compatible with GAP 4.3.
#############################################################################
License and Installing GAP 4.4
------------------------------
GAP is free software which is distributed under the GNU general public
licence. You can get GAP 4.4 from
- http://www.gap-system.org
- ftp://ftp.gap-system.org in the directory pub/gap/gap4.
#############################################################################
Acknowledgements
---------------
* Personal Support
The members of the GAP development team are working on GAP as a part of
their research or in their free time. The GAP development team has members
all over the world and thus GAP can be considered as a world wide joint
research project. A list of the members of the GAP development team can
be found in the Tutorial manual of GAP.
A significant part of the functionality of GAP is available in the GAP
packages. These are independently developed packages of code with their
own author lists. A detailed list of the available GAP packages can be
found on the GAP web pages.
Finally, there is a long list of collaborateurs and users of GAP. The
feedback and constructive critism of these people has helped to fix bugs
and to improve the system. Many thanks are due to all these people.
* Financial Support
We acknowledge with gratitude the support of the development of GAP
provided by a variety of funding bodies. Details can be found on the GAP
web pages.
############################################################################
Bugfixes
--------
If you have followed the releases of GAP over the last years you might
have noted that a first bugfix typically comes early after a release. This
is despite of extensive testing, but unfortunately reflects the limited
size of the developer group compared to the user community. We simply
might not have thought of doing certain things. If the experience of
previous releases holds, we therfore will have a first update within the
next two or three weeks. You might want to plan accordingly.
From sal at dcs.st-and.ac.uk Fri Apr 16 22:56:39 2004
From: sal at dcs.st-and.ac.uk (Steve Linton)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Release -- A Couple of Details
Message-ID: <20040416225639.3c72f371@caolila.dcs.st-and.ac.uk>
Dear GAP Forum,
Just a few points to follow the release announcement.
Firstly, due to some glitches here, the Website and FTP site were not fully
updated with the intended new contents until this afternoon. In particular,
the packages archive briefly contained a broken version of the xmod
package. These sites are now updated. Apologies to anyone affected. As you will
see the Website is still somewhat transitional, containing pages with both old
and new "look". Over the next months we should complete the move to the new
style. We would welcome comments on this style.
Secondly, as ever, a few minor bugs came to light too late in the release
process for fixes to be safely included in the release, and will be fixed in a
bugfix in the next week or so. If any of them cause you especial difficulties,
we may be able to send a specific correction to you.
1. A bug in the on-line help functions causes errors displaying a very few
sections of the manual using the "screen" viewer.
2. There is a bug when computing homomorphisms from a finitely-presented group
with a generator that occurs in no relator, which can cause an error..
3. When GAP is loaded from a saved workspace, user specific information (such
as the home directory referred to by ~) is taken from the workspace, not from
the loading user. Thus if user a saves a workspace, and user b loads it and
then does Read("~/myfuncs.g"); it will try to load "/home/a/myfuncs.g".
4. Runtimes() under Windows reports 0 instead of fail for the unavailable
system and child CPU times.
Finally, I'd like to take this opportunity to thank everyone concerned for
their hard work in the long process of preparing this release.
Steve Linton
--
Steve Linton School of Computer Science &
Centre for Interdisciplinary Research in Computational Algebra
University of St Andrews Tel +44 (1334) 463269
http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278
From bcolletti at compuserve.com Sun Apr 18 15:46:57 2004
From: bcolletti at compuserve.com (Bruce W. Colletti)
Date: Fri Apr 8 15:25:39 2005
Subject: [GAP Forum] Writing to File
Message-ID: <002601c42554$012d67d0$6501a8c0@bcolletti>
Re GAP 4.3fix4 running under WinXP Home.
How do I set the record length of an output text file?
When printing to the file, numbers follow one another (as desired) until too many occur, at which time GAP automatically creates a new output line. Numbers are separated by a space or tab.
LogTo("filename") opens the file...maybe that's the problem. If so, what else should I use? I've tried an example in the manual that starts:
name := Filename(DirectoryTemporary(),"test");
but GAP gags on the DirectoryTemporary() command.
Thanks.
Bruce
From gap at gap.zssm.zp.ua Sun Apr 18 19:10:01 2004
From: gap at gap.zssm.zp.ua (Alexander Konovalov)
Date: Fri Apr 8 15:25:40 2005
Subject: [GAP Forum] Writing to File
In-Reply-To: <002601c42554$012d67d0$6501a8c0@bcolletti>
References: <002601c42554$012d67d0$6501a8c0@bcolletti>
Message-ID: <636591620.20040418201001@gap.zssm.zp.ua>
Dear Bruce,
if I understand your task perfectly, you would like to write certain
information to the text file and you need to increase the number of
symbols per line in the output file.
There are several approaches to this.
The simplest, but less flexible is to use 'LogTo("filename");'
and it will just copy the output from the screen to the file.
In this case you may use the command 'SizeScreen([256,]);' to
reach the maximum possible length of the line, but no more than 256
symbols.
More opportunities are provided by using streams, and it is very
useful that your are already looking in this direction. Indeed,
'DirectoryTemporary()' works only for UNIX-type systems, but this
function is not essential in reaching your aims. In the example you
cited this function is used to create a filename in the temporary
directory, but you may enter the next command from this example in the
form
output := OutputTextFile( "filename", true );;
and it will create the file "filename" just in your current directory.
Line length in this file can also be regulated by the SizeScreen
command - it will be changed on screen and in the stream
simultaneously.
You could also be interested *** to have all output in one single line
of text without line breaks *** - in conditions above, this may be
achieved entering the command
SetPrintFormattingStatus( out, false )
Hope this helps.
Sincerely yours,
Alexander Konovalov
On Sunday, April 18, 2004 at 4:46:57 PM
Bruce W. Colletti wrote:
> Re GAP 4.3fix4 running under WinXP Home.
> How do I set the record length of an output text file?
> When printing to the file, numbers follow one another (as desired) until too many occur, at which time GAP automatically creates a new output line. Numbers are separated by a space or tab.
> LogTo("filename") opens the file...maybe that's the problem. If so, what else should I use? I've tried an example in the manual that starts:
> name := Filename(DirectoryTemporary(),"test");
> but GAP gags on the DirectoryTemporary() command.
> Thanks.
> Bruce
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
From costanti at science.unitn.it Sun Apr 18 18:24:51 2004
From: costanti at science.unitn.it (Marco Costantini)
Date: Fri Apr 8 15:25:40 2005
Subject: [GAP Forum] Writing to File
In-Reply-To: <002601c42554$012d67d0$6501a8c0@bcolletti>
References: <002601c42554$012d67d0$6501a8c0@bcolletti>
Message-ID: <1082309091.4082b9e35b4f2@www.unitn.it>
Dear Bruce and gap-forum,
Scrive "Bruce W. Colletti" :
> Re GAP 4.3fix4 running under WinXP Home.
>
> How do I set the record length of an output text file?
>
> When printing to the file, numbers follow one another (as desired) until too
> many occur, at which time GAP automatically creates a new output line.
Try something like
AppendToFile := function ( file, s )
local otf;
otf := OutputTextFile( file, true );
SetPrintFormattingStatus( otf, false );
AppendTo( otf, s );
CloseStream( otf );
end;
Where s is what you want to write in the file
> Numbers are separated by a space or tab.
>
> LogTo("filename") opens the file...maybe that's the problem. If so, what
> else should I use? I've tried an example in the manual that starts:
>
> name := Filename(DirectoryTemporary(),"test");
>
> but GAP gags on the DirectoryTemporary() command.
What do you mean with "gags"?
Try an other directory.
Best,
Marco
From wh at icparc.ic.ac.uk Mon Apr 19 18:21:22 2004
From: wh at icparc.ic.ac.uk (Warwick Harvey)
Date: Fri Apr 8 15:25:40 2005
Subject: [GAP Forum] Finding a representative which moves fewest points
In-Reply-To: <200404011850.i31IoIMd010540@schur.math.colostate.edu>;
from hulpke@math.colostate.edu on Thu, Apr 01, 2004 at 11:50:18AM
-0700
References: <20040401003727.A9726@tempest.icparc.ic.ac.uk>
<200404011850.i31IoIMd010540@schur.math.colostate.edu>
Message-ID: <20040419182121.A26952@tempest.icparc.ic.ac.uk>
Dear Alexander, dear GAP Forum,
Thanks for your feedback.
On Thu, Apr 01, 2004 at 11:50:18AM -0700, Alexander Hulpke wrote:
> Warwick Harvey asked:
>
> > What I would like is a function like RepresentativeAction which returns a
> > representative that moves as few points as possible. Taking the example
> > from the manual:
> >
> > gap> g:=Group((1,3,2),(2,4,3));;
> > gap> RepresentativeAction(g,1,3);
> > (1,3)(2,4)
> >
> > I would like instead the element (1,3,2), since this only moves 3 points
> > rather than 4. I tried constructing cosets of the stabilizer of 1 and using
> > RepresentativeSmallest on the appropriate coset, but of course the notion of
> > smallest there is not what I want.
>
> Basically you want to find an element x in the stabilizer of 3 so that r*x
> fixes many points. If your group is of moderate degree, probvably the
> following brute-force approach works:
Thanks. Unfortunately, by the time I apply it to real problems, a brute
force search is out of the question. The first real problem I tried it on
required solving a sequence of a couple of hundred such problems on groups
growing to size 2e35 (large base groups with lots of block structure).
> If your group gets bigger so that you do not want to run through all
> elements in s, I would consider to map some points according to the orbits
> of s.
Indeed. In the last couple of weeks I have developed a backtracking search
algorithm which appears to be quite effective; each of the above instances
is solved in less than a minute, often under a second (1.7GHz Centrino
processor). The minimal representatives had between 52 and 260 moved points
out of 1170. The real key was finding a good lower bound on the number of
points that must be moved in a representative. If anybody is interested in
the details I am happy to pass them on.
One thing I noticed while working on this which surprised me (probably just
my naivete) was that something like RepresentativeAction(g, 1, 2) was
significantly slower than Orbit(g, 1) - at least for my groups. Presumably
the algorithm that RepresentativeAction uses is a general one, and there's
no specialisation for this easy case. (Either that, or Orbit is doing
something smarter than I expected.) (This is using 4.3 - I haven't tried
4.4 yet.)
Cheers,
Warwick
From heckenb at mi.uni-erlangen.de Tue Apr 20 00:43:14 2004
From: heckenb at mi.uni-erlangen.de (Frank Heckenbach)
Date: Fri Apr 8 15:25:40 2005
Subject: [GAP Forum] Bug in Process()
Message-ID: <200404192343.BAA10287@goedel.fjf.gnu.de>
Dear Gap-Forum,
it seems to become a tradition for me to find a bug related to
Process() in each new release. ;-) With GAP 4.4.2 I see this:
gap> s := "";;
gap> out := OutputTextString (s, true);;
gap> inp := InputTextFile ("/dev/null");;
gap> Process (DirectoryCurrent(), "/bin/true", inp, out, []);;
gap> DirectoryTemporary ();;
gap> Process (DirectoryCurrent(), "/bin/true", inp, out, []);;
List Element: must be a list (not a boolean) at
return ExecuteProcess( dir, prg, input![1], output![1], args );
called from
EXECUTE_PROCESS_FILE_STREAM( dir, prg, input, new_output, args ) called from
( ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can replace via 'return ;' to continue
The problem seems to be the caching of `PROCESS_INPUT_TEMPORARY' and
`PROCESS_OUTPUT_TEMPORARY' in `process.gi' while the corresponding
files are erased. `TmpName' or `DirectoryTemporary' then seem to
reuse the name (I assume this is intended).
If it's reused as a directory which still exists (like here), this
will fail and result in `new_output = fail', leading to the error
shown. (If it's reused as a file, it may silently overwrite that
file; I haven't checked this case.)
Quick fix:
--- gap4r4/lib/process.gi.orig Mon Apr 19 03:22:39 2004
+++ gap4r4/lib/process.gi Mon Apr 19 03:31:20 2004
@@ -148,9 +148,6 @@
#M Process( , , ,