Dies ist eine Beschreibung der Funktionen aus "zusammenstellung.g". Angefertigt von Christian Ringe, Lehrstuhl D für Mathematik, RWTH Aachen. Aachen, im Januar 2008. Der Autor hat diese Funktionen in den Jahren 2004-2007 anläßlich seiner Dissertation "Über die Elementarteiler der Inzidenzmatrix des Ree-Unitals" entwickelt, welche irgendwann im Jahr 2008 erscheinen wird. Einige Hinweise vorab: --> Die Datei "zusammenstellung.g" muss 2 Mal eingelesen werden, da die Funktionen nicht in der benötigten Reihenfolge stehen. --> Es ist gelegentlich hilfreich, auch die Kommentare in "zusammenstellung.g" zu beachten. --> Dem Autor sind keine logischen Fehler in den Funktionen bekannt. Dennoch übernimmt er keine Garantie dafür, dass es wirklich keine Fehler gibt. --> Möglicherweise sind einige der Funktionen an einigen Stellen nicht sonderlich geschickt implementiert worden. Der Autor bittet hierfür um Nachsicht. 1. Funktion "ElemDivisors" -------------------------- Eingabe: 1. Eine Integer-Matrix A. 2. Deren Rang. 3. Eine Primzahl p. 4. Die Zeilenlänge n. 5. Eine p-Potenz, modulo derer reduziert wird. Ausgabe: Eine Liste der Länge 4, deren 2. Komponente die Liste der r_i (aus dem Artikel von Frank Lübeck) enthält, und deren 4. Komponente die p-Anteile der Elementarteiler von A enthält (mit Vielfachheiten). Beschreibung: Es handelt sich um eine Implementation des Algorithmus aus dem Artikel "On the Computation Elementary Divisors of Integer Matrices" von Frank Lübeck. Dabei wurden folgende Modifikationen eingebaut: --> Um die "entry explosion" zu vermeiden, werden die Eintraege zwischendurch modulo einer p-Potenz reduziert. Falls diese p-Potenz zu klein ist, liefert der Algorithmus keine korrekten Ergebnisse. --> Um Speicherplatz zu sparen, wird noch folgender Trick verwendet, der bei dünn besetzten Inzidenzmatrizen recht nützlich ist: -->Falls eine Zeile (in "Vektor-Form") nur aus Nullen und Einsen besteht, werden lediglich die Indizes der Eins-Einträge gespeichert ("Mengen-Form"). Die Funktion erkennt anhand der Zeilenlänge, ob "Vektor-Form" oder "Mengen-Form" vorliegt. Natürlich können hier theoretisch Fehler auftreten, wenn z.B. der "Alles-1-Vektor" auftritt. In den vom Autor anlässlich seiner Dissertation betrachteten Fällen passiert das jedoch nicht. Das Umwandeln zwischen "Vektor-Form" und "Mengen-Form" übernehmen die Hilfsfunktionen "Vector2Set" und "Set2Vector". --> Das Berechnen der Elementarteiler aus der Liste der r_i aus dem Artikel übernimmt die Hilfsfunktion "ElemDivChange2". 2. Funktion "NextHigher" ------------------------ Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivChange2" verwendet wird. Siehe auch die entsprechenden Kommentare in "zusammenstellung.g". 3. Funktion "ElemDivChange2" ---------------------------- Eingabe: 1. Die Liste der r_i, die innerhalb der Funktion "ElemDivisors" ermittelt wird. 2. Die Primzahl p, die als Parameter in "ElemDivisors" vorliegt. Ausgabe: Liste der p-Anteile der Elementarteiler. Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivisors" verwendet wird. 4. Funktion "Vector2Set" ------------------------ Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivisors" verwendet wird. Siehe auch die entsprechenden Kommentare in "zusammenstellung.g". 5. Funktion "Set2Vector" ------------------------ Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivisors" verwendet wird. Siehe auch die entsprechenden Kommentare in "zusammenstellung.g". 6. Funktion "OneZeroTest" ------------------------- Eingabe: Eine Liste. Ausgabe: true/false. Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivisors" verwendet wird. Sie liefert "true", falls die Liste nur Eintraege 0 oder 1 hat. Ansonsten liefert sie "false". 7. Funktion "FixedPoints" ------------------------- Eingabe: 1. Eine natürliche Zahl n. 2. Eine Permutation tau auf [1..n]. Ausgabe: Diejenigen Elemente von [1..n], die von tau fixiert werden. Motivation: Die Punkte einer Geraden des Ree-Unitals sind genau die Fixpunkte einer Involution der Ree-Gruppe. 8. Funktion "DesiredOrder" -------------------------- Eingabe: 1. Eine Gruppe G. 2. Eine natürliche Zahl k. Ausgabe: Ein zufälliges Element von G der Ordnung k. Bemerkung: Wenn solche Elemente sehr selten (bzw. nicht vorhanden) sind, muss man natürlich sehr lange (bzw. bis zum Sankt-Nimmerleinstag ;-) ) warten. Motivation: s. "FixedPoints". 9. Funktion "ElemDivisorsNeu" ----------------------------- Beschreibung: Dies ist eine Weiterentwicklung von "ElemDivisors". Der Algorithmus ist praktisch der Gleiche, mit einer einzigen Modifikation: Während in "ElemDivisors" Vektoren mit 0-1-Einträgen in die "Mengen-Form" eingepackt werden, werden in "ElemDivisorsNeu" Vektoren mit weniger als 10 verschiedenen Einträgen eingepackt, und zwar in die Form --> Liste von Paaren; ein Paar ist [Eintrag, Liste von Indizes mit diesem Eintrag] Motivation: Dies ist eine Lösung, die gut bei dünn besetzten Matrizen mit wenigen verschiedenen Einträgen funktioniert. Die Bahn des Hauptdivisors (x) erfüllt dieses (zumindest im Fall q=27). 10. Funktion "PackEin" ---------------------- Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivisorsNeu" verwendet wird. Die Bedeutung ist selbsterklärend. 11. Funktion "PackAus" ---------------------- Beschreibung: Hilfsfunktion, die von der Funktion "ElemDivisorsNeu" verwendet wird. Die Bedeutung ist selbsterklärend. 12. Funktion "RandomSubset" --------------------------- Eingabe: Zwei natürliche Zahlen n, m. Ausgabe: Eine zufällig ausgewählte Teilmenge von [1..n] der Mächtigkeit m. Motivation: Im Fall q=27 treten Matrizen mit mehreren 100.000 Zeilen auf, deren Rang aber nur ca. 19.700 ist. Es ist daher nicht sinnvoll, die komplette Matrix abzuarbeiten. Zufällig ausgewählte 20.000 Zeilen genügten in den vom Autor betrachteten Fällen. 13. Funktion "TheUltimateStabFinder" ------------------------------------ Eingabe: 1. Die Ree-Gruppe G=R(q) als Permutationsgruppe auf der Punktemenge. 2. Der Parameter q. 3. Zwei verschiedene Punkte (d.h. Zahlen). Ausgabe: 1. Der Stabilisator des Hauptdivisors (x). 2. Der Stabilisator des Hauptdivisors (y1). 3. Der Stabilisator des Hauptdivisors (y2). Beschreibung: Es handelt sich um eine Implementation des Algorithmus aus der Dissertation des Autors. Siehe Unterabschnitt 4.5.3 der erwähnten Arbeit, sobald diese erschienen ist. 14. Funktion "Wandler" ---------------------- Eingabe: Zwei Listen von Zahlen. Ausgabe: Das entsprechende Element aus der Bahn von (x), und zwar in einer Form, die die Funktion "ElemDivNeu" verarbeiten kann. Beschreibung/Motivation: "Wandler" ist speziell für den Fall q=27 geschrieben. In diesem Fall besteht der Hauptdivisor (x) aus q^2=729 Einträgen 1 und einem Eintrag -q^2=-729. Die Funktion ist daher so angelegt, dass eine der beiden Eingabelisten die Länge 1 hat, die andere die Länge 729. Alles andere führt zu Unsinn. Man ermittelt die beiden Eingabelisten wie folgt: --> Zuerst ermittelt man den Stabilisator Sx von (x) mit der Funktion "TheUltimateStabFinder". --> Dann stellt man fest, dass Sx auf [1..q^3+1]=[1..19684] genau eine Bahn der Länge 1 hat, und genau eine Bahn der Länge 729. --> Diese beiden Bahnen sind die gesuchten Eingabelisten. Bemerkung: Die in den Kommentaren in "zusammenstellung.g" erwähnten 200 Elemente können mitunter zu wenig sein, um die Gruppe P1001 zu erzeugen. In dem Fall kommt eine Fehlermeldung. Dann die Funktion einfach noch mal laufen lassen, irgendwann reicht es sicher. 15. Funktion "BahnMacher" ------------------------- Eingabe: 1. Eine Permutationsgruppe G auf [1..n]. 2. Eine Menge von Mengen von Punkten aus [1..n]. Name: setset. 3. Eine Obergrenze grenze. Ausgabe: Eine zufällig ausgewählte Teilbahn von setset der Mächtigkeit grenze. Beschreibung/Motivation: setset ist die Menge, die aus den beiden Eingabelisten von "Wandler" besteht. Ziel ist es, eine Teilmenge gewünschter Mächtigkeit (z.B. 20.000) der Bahn von (x) zu gewinnen. Die gesamte Bahn hat eine Länge > 500.000, daher ist es nicht praktikabel, damit zu arbeiten. Die Ausgabe von "BahnMacher" sollte mit "Wandler" bearbeitet werden. Anschließend kann man diese Liste als Eingabematrix von "ElemDivNeu" verwenden. Auf diese Weise wurde das Ergebnis des Abschnitts 5.7 der Dissertation des Autors gewonnen. 16. Funktion "PermOrbit" ------------------------ s. Kommentare in "zusammenstellung.g"