[1XGAP 4 Package [5Xorb[0m[1X[0m [1Xorb --- Methods to enumerate Orbits[0m Version 2.0 June 2008 Jürgen Müller Max Neunhöffer Felix Noeske Jürgen Müller Email: [7Xmailto:juergen.mueller@math.rwth-aachen.de[0m Homepage: [7Xhttp://www.math.rwth-aachen.de/~Juergen.Mueller[0m Address: Lehrstuhl D für Mathematik, RWTH Aachen, Templergraben 64, 52062 Aachen, Germany Max Neunhöffer Email: [7Xmailto:neunhoef@mcs.st-and.ac.uk[0m Homepage: [7Xhttp://www-groups.mcs.st-and.ac.uk/~neunhoef[0m Address: School of Mathematics and Statistics Mathematical Institute University of St Andrews North Haugh St Andrews, Fife KY16 9SS Scotland, UK Felix Noeske Email: [7Xmailto:felix.noeske@math.rwth-aachen.de[0m Homepage: [7Xhttp://www.math.rwth-aachen.de/~Felix.Noeske[0m Address: Lehrstuhl D für Mathematik, RWTH Aachen, Templergraben 64, 52062 Aachen, Germany ------------------------------------------------------- [1XCopyright[0m © 2005-2008 by Jürgen Müller, Max Neunhöffer and Felix Noeske This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see [7Xhttp://www.gnu.org/licenses/[0m. ------------------------------------------------------- [1XContents (orb)[0X 1 Introduction 1.1 Motivation for this package 1.2 Overview over this manual 2 Installation of the [5Xorb[0m-Package 3 Basic orbit enumeration 3.1 Enumerating orbits 3.1-1 Orb 3.1-2 Enumerate 3.1-3 IsClosed 3.1-4 Options for orbits 3.1-5 Output components of orbits 3.1-6 StabWords 3.1-7 PositionOfFound 3.1-8 DepthOfSchreierTree 3.1-9 ActionOnOrbit 3.1-10 OrbActionHomomorphism 3.1-11 TraceSchreierTreeForward 3.1-12 TraceSchreierTreeBack 3.1-13 ActWithWord 3.1-14 EvaluateWord 3.1-15 AddGeneratorsToOrbit 3.1-16 MakeSchreierTreeShallow 3.1-17 FindSuborbits 3.1-18 OrbitIntersectionMatrix 4 Hashing techniques 4.1 The idea of hashing 4.2 Hash functions 4.2-1 ChooseHashFunction 4.2-2 ChooseHashFunction 4.2-3 ChooseHashFunction 4.2-4 ChooseHashFunction 4.2-5 ChooseHashFunction 4.2-6 ChooseHashFunction 4.2-7 ChooseHashFunction 4.2-8 ChooseHashFunction 4.2-9 ChooseHashFunction 4.2-10 ChooseHashFunction 4.2-11 ChooseHashFunction 4.3 Using hash tables 4.3-1 NewHT 4.3-2 AddHT 4.3-3 ValueHT 4.3-4 InitHT 4.3-5 GrowHT 4.4 The data structures for hash tables 4.4-1 Memory requirements 4.4-2 Handling of collisions 4.4-3 Efficiency 5 Caching techniques 5.1 The idea of caching 5.2 Using caches 5.2-1 LinkedListCache 5.2-2 CacheObject 5.2-3 ClearCache 5.2-4 UseCacheObject 6 Random elements 6.1 Randomizing mutable objects 6.1-1 Randomize 6.1-2 MakeRandomVectors 6.1-3 MakeRandomLines 6.2 Product replacement 6.2-1 ProductReplacer 6.2-2 Next 6.2-3 Reset 7 Searching in groups and orbits 7.1 Searching using orbit enumeration 7.2 Random searches in groups 7.2-1 RandomSearcher 7.2-2 Search 7.3 The dihedral trick and applications 7.3-1 FindInvolution 7.3-2 FindCentralisingElementOfInvolution 7.3-3 FindInvolutionCentralizer 7.4 Orbit statistics on vector spaces 7.4-1 OrbitStatisticOnVectorSpace 7.4-2 OrbitStatisticOnVectorSpaceLines 7.5 Finding generating sets of subgroups 7.5-1 FindShortGeneratorsOfSubgroup 8 Orbit enumeration by suborbits 8.1 [10XOrbitBySuborbits[0m and its resulting objects 8.1-1 OrbitBySuborbit 8.1-2 OrbitBySuborbitKnownSize 8.1-3 Size 8.1-4 Seed 8.1-5 SuborbitsDb 8.1-6 WordsToSuborbits 8.1-7 Memory 8.1-8 Stabilizer 8.1-9 StabWords 8.1-10 SavingFactor 8.1-11 TotalLength 8.1-12 Representatives 8.1-13 SavingFactor 8.1-14 OrigSeed 8.2 Preparation functions for [2XOrbitBySuborbit[0m ([14X8.1-1[0m) 8.2-1 OrbitBySuborbitBootstrapForVectors 8.2-2 OrbitBySuborbitBootstrapForLines 8.2-3 OrbitBySuborbitBootstrapForSpaces 8.3 Data structures for orbit-by-suborbits 8.3-1 IsOrbitBySuborbitSetup 8.3-2 The global record [10XORB[0m 8.4 Lists of orbit-by-suborbit objects 8.4-1 InitOrbitBySuborbitList 8.4-2 IsVectorInOrbitBySuborbitList 8.4-3 OrbitsFromSeedsToOrbitList 8.4-4 VerifyDisjointness 8.4-5 Memory 8.4-6 TotalLength 8.4-7 Size 8.4-8 SavingFactor 9 Finding nice quotients 10 Examples 10.1 The Mathieu group M_{11} acting in dimension 24 10.2 The Fischer group Fi_{23} acting in dimension 1494 10.3 The Conway group Co_1 acting in dimension 24 10.4 The Baby Monster B acting on its 2A involutions -------------------------------------------------------