Umfangreichere Programmieraufgabe:

Berechnung von Elementen der kristallinen Basis der Quantengruppe U_{q}^{+}(sl_{n})

Dirk Dudek BUGH Wuppertal

dudek@rz.uni-wuppertal.de

Jens Bender BUGH Wuppertal

                            bender@rz.uni-wuppertal.de

März 1998 — April 1998

Zusammenfassung

Dieses Papier stellt eine Dokumentation der umfangreicheren Programmieraufgabe dar. Es handelt sich dabei um ein Programm, dessen Aufgabe es ist, Basiswechselkoeffizienten zwischen der kristallinen Basis und der PBW– Basis der Gruppe U_{q}^{+}(sl_{n}) zu berechnen. Der zugrundeliegende Algorithmus wird von der Theorie der Quantengruppen geliefert.

Dokumentation — \begin{matrix}c \\ ◯ \end{matrix} 1998 by 𝔇irk 𝔇udek & Jens Bender 2

Inhaltsverzeichnis

1 Mathematischer Hintergrund 3 1.1 Die PBW–Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Die kanonische beziehungsweise kristalline Basis . . . . . . . . . . . 4 1.3 Basiswechsel zwischen kristalliner Basis und PBW–Basis . . . . . . 5

2 Der Algorithmus 6 2.1 Reduktion von ζ nach ω . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Reduktion von ω nach γ . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Reduktion von γ nach c . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Berechnung der Koeffizienten c_{i}^{r}(M, M_{a}) . . . . . . . . . . . . . . . 10

3 Das Programm 11 3.1 Anforderungen an das Programm . . . . . . . . . . . . . . . . . . . 11 3.2 Wahl der Programmiersprache . . . . . . . . . . . . . . . . . . . . 11 3.3 Aufruf und Benutzung . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Umsetzung des Algorithmus in Programmtext . . . . . . . . . . . . 14 3.6 Probeläufe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Die Darstellung des mathematischen Hintergrunds und des Algorithmus folgt weitgehend den Notizen von Markus Reineke.

1 Mathematischer Hintergrund

Ein zentrales Objekt in der Theorie der Quantengruppen ist die folgende Algebra, der sogenannte positive Teil der ”Drinfeld–Jimbo–Quantisierung der universellen Einhüllenden der Lie–Algebra sl_{n}“.

Definition 1.1:

U_{q}^{+}(sl_{n}) bezeichne die ℚ(v)–Algebra mit Erzeugenden E_{i}, i = 1, ⋯, n und Relationen

E_{i} E_{j} = E_{j} E_{i} falls |i − j| ≥ 2
E_{i}^{2} E_{j} − (v + v^{−1}) E_{i} E_{j} E_{i} + E_{j} E_{i}^{2} = 0 falls |i − j| = 1.

Das heißt, U_{q}^{+}(sl_{n}) ist die freie assoziative ℚ(v)–Algebra in den Erzeugenden E_{i} modulo dem durch die Relationen erzeugten zwei-seitigen Ideal.

Eines der Ziele der Theorie der Quantengruppen ist es, die Struktur dieser Algebra möglichst genau zu verstehen. Hierzu ist es sinnvoll, in einem gewissen Sinne ”gute“ Basen von U_{q}^{+}(sl_{n}) als (unendlich-dimensionalen) ℚ(v)–Vektorraum zu finden. Zwei solche Basen werden durch relativ tiefliegende Sätze von Ringel beziehungsweise Lusztig geliefert.

1.1 Die PBW–Basis

Ringel konstruiert wie folgt eine Algebra H_{q}(Q) aus der Darstellungstheorie des Köchers

Q = A_{n} : \xymatrix{1 \ar[r] & 2 \ar[r] & 3 \ar[r] & ⋯ \ar[r] & n} .

Sei H_{q}(Q) der ℚ(v)–Vektorraum mit Basis

{E_{[M]} | [M] Isomorphieklasse einer endlich–dimensionalen Q–Darstellung}

wobei der Grundkörper 𝕜 beliebig sei. Definiere auf H_{q}(Q) eine Multiplikation wie folgt:

E_{[M]} · E_{[N]} := ∑_{[X]} v^{[M,M]+[N,N]+<\underline{dim} M,\underline{dim} N>−[X,X]} · F_{MN}^{X}(v^{2}) · E_{[X]}.

Dabei bezeichnet

[A, B] := dim_{𝕜} Hom_{𝕜Q}(A, B)

und

< d_{1}, d_{2} >= ∑_{i=1}^{n}(d_{1})_{i} · (d_{2})_{i} − ∑_{i=1}^{n−1}(d_{1})_{i} · (d_{2})_{i+1}

für d_{1}, d_{2} ∈ ℕ^{n} die (nicht–symmetrische) Eulerform. Ferner sei F_{MN}^{X}(v^{2}) ∈ ℤ[v] das sogenannte Hall–Polynom:

Da die Darstellungstheorie eines Dynkin–Köchers nicht vom Grundkörper 𝕜 abhängt (die Unzerlegbaren sind immer durch positive Wurzeln klassifiziert), kann man Q–Darstellungen über jedem Körper realisieren. Also kann man

F_{MN}^{X}(q) = #{U ⊂ X | U ≅ N, X/_{U} ≅ M über 𝔽_{q}}

für jede Primzahlpotenz q definieren. Tatsächlich setzt sich diese Funktion zu einem Polynom in ℤ[q] fort.

Man zeigt nun, daß H_{q}(Q) mit obigem Produkt tatsächlich eine assoziative Algebra bildet. Ringels Hauptsatz lautet:

Theorem 1.1: (Ringel)

Die Zuordnung

η : U_{q}^{+}(sl_{n}) ⟶ H_{q}(Q) mit E_{i} ↦ E_{[E_{i}]}

setzt sich zu einem Isomorphismus von ℚ(v)–Algebren fort.

Dabei ist E_{i} die einfache Q–Darstellung zum Punkt i.

Also kann man durch

E_{[M]} := η^{−1}(E_{[M]}) ∈ U_{q}^{+}(sl_{n})

eine Basis von U_{q}^{+}(sl_{n}), die sogenannte PBW–Basis

B := {E_{[M]} ∈ U_{q}^{+}(sl_{n}) | [M] Isomorphieklasse einer endlich–dim. Q–Darstellung}

definieren. Prinzipiell ist die Struktur von U_{q}^{+}(sl_{n}) damit bekannt, denn das Produkt von Basiselementen läßt sich komplett aus der Darstellungstheorie des Köchers Q bestimmen.

Aber: Die Berechnung von Hall–Polynomen ist im allgemeinen äußerst schwierig!

1.2 Die kanonische beziehungsweise kristalline Basis

Die Algebra U_{q}^{+}(sl_{n}) besitzt einen Automorphismus , der durch

\overline{E_{i}} := E_{i} für alle i = 1, …, n

und

\overline{v} := v^{−1}

gegeben ist. Die Zuordnung ist ein ℚ–linearer (oder auch ”ℚ(v)–semilinearer“) Algebrenautomorphismus. Damit läßt sich der folgende Satz von Lusztig formulieren.

Theorem 1.2: (Lusztig)

Es gibt genau eine Basis B von U_{q}^{+}(sl_{n}) mit

i) \overline{b} = b für alle b ∈ B.

ii) Schreibt man

b = ∑_{[M]} c_{M}E_{[M]},

so gibt es genau ein [M_{0}] mit

c_{M_{0}} = 1  und  c_{M} ∈ v^{−1} ℤ[v^{−1}] für alle M ≅ M̸_{0}.

Die Eindeutigkeit einer solchen Basis ist leicht einzusehen. Die Existenz dagegen ist ein sehr tiefliegendes Ergebnis, für das man die Struktur von U_{q}^{+}(sl_{n}) und der PBW–Basis B sehr genau analysieren muß.

Die kristalline Basis B sieht sehr unscheinbar aus. Ihre Existenz hat allerdings enorme Konsequenzen! So lassen sich mit B zum Beispiel alle Fragen zur endlichdimensionalen Darstellungstheorie der Lie–Algebra sl_{n} beziehungsweise der Gruppe SL_{n}(ℂ) auf kombinatorische Probleme reduzieren.

1.3 Basiswechsel zwischen kristalliner Basis und PBW–Basis

Eines der Hauptprobleme in der Theorie der kristallinen Basis B ist, daß ihre Kombinatorik zwar gut verstanden ist, ihre einzelnen Elemente aber unbekannt sind (außer für n = 2 und n = 3).

Man ist besonders an den Basiswechselkoeffizienten zwischen B und B interessiert, da man die PBW–Basis B als ”verstanden“ annimmt.

Folgendes ist darüber bekannt:

Zunächst einmal kann man nach der zweiten Bedingung in Lusztigs Theorem jedem Element aus B eine Isomorphieklasse einer endlich–dimensionalen Q–Darstellung zuordnen. Also hat man eine Parametrisierung von B gefunden und setzt daher

B = {E_{[M]} | [M] Isomorphieklasse einer endlich–dimensionalen Q–Darstellung}.

Dann gilt:

Satz 1.3: (Lusztig)

Schreibt man

E_{[M]} = ∑_{[N]} ζ_{N}^{M}E_{[N]},

so gilt

a) ζ_{N}^{M} ≠ 0 ⇒ M ≤_{deg} N (Entartungen von 𝕜Q–Moduln).

b) ζ_{M}^{M} = 1.

c) ζ_{N}^{M} ∈ v^{−1} ℤ[v^{−1}] für alle M ≤_{deg} N mit M ≅ N̸.

d) v^{[N,N]−[M,M]} · ζ_{N}^{M} ∈ ℕ[v^{2}] ist ein Polynom in v^{2}, dessen Koeffizienten die Dimensionen der ”Schnitt-Kohomologiegruppen“ des Orbitabschlusses \overline{O_{M}} am Punkt N sind.

Der letzte Punkt im Satz benötigt tiefliegende Methoden der algebraischen Geometrie (”Weil–Vermutungen“, ”perverse Garben“), zeigt aber einen Zusammenhang zwischen der Struktur von U_{q}^{+}(sl_{n}) und der Geometrie von Köcherdarstellungen auf.

2 Der Algorithmus

Durch explizite Berechnung einiger spezieller Hall–Polynome ist es kürzlich Markus Reineke^{1} gelungen einen Algorithmus zur Berechnung der Polynome ζ_{N}^{M} (also der Basiswechselkoeffizienten) anzugeben.

2.1 Reduktion von ζ nach ω

Im ersten Schritt definiere die Laurent–Polynome ω_{N}^{M} ∈ ℤ[v, v^{−1}] durch

\overline{E_{[M]}} = ∑_{[N]} ω_{N}^{M}E_{[N]}.

Wieder gelten:

a) ω_{N}^{M} ≠ 0 ⇒ M ≤_{deg} N.

b) ω_{M}^{M} = 1.

Die Polynome ζ_{N}^{M} lassen sich aus den ω_{N}^{M} durch Auflösung einer Rekursion über die Entartungsordnung ≤_{deg} berechnen:

1Manuskript

Lemma 2.4:

Angenommen es sind bekannt

a) Alle Koeffizienten ω_{N}^{M}.

b) Alle Polynome ζ_{L}^{M} mit M ≤_{deg} L <_{deg} N.

Dann findet man die Polynome ζ_{N}^{M} wie folgt: Schreibe

∑_{L: M≤_{deg}L<_{deg}N} \overline{ζ_{L}^{M}} · ω_{N}^{L} = ∑_{k∈ℤ}a_{k} v^{k}.

Dann gilt:

ζ_{N}^{M} = ∑_{k<0} a_{k} v^{k}.

Damit läuft die Rekursion durch, denn der Anfang ζ_{M}^{M} = 1 ist bekannt.

Bleibt noch das Problem, die Entartungsordnung explizit zu machen. Hierzu benötigt man einen Satz von Bongartz und ein Lemma von Riedtmann.

Theorem 2.5: (Bongartz)

M ≤_{deg} N ⇔ [M, U] ≤ [N, U]

für alle unzerlegbaren 𝕜Q–Moduln U.

Die Unzerlegbaren und die Dimensionen von Homomorphismenräumen zwischen Unzerlegbaren sind für Q = A_{n} bekannt. Es gilt nämlich:

E_{ij} : \xymatrix{0 \ar[r]^{0} & ⋯ \ar[r]^{0} & 0 \ar[r]^{0} & 𝕜 \ar[r]^{1} & ⋯ \ar[r]^{1} & 𝕜 \ar[r]^{0} & 0 \ar[r]^{0} & ⋯ \ar[r]^{0} & 0 \\ & & & i \ar[u] & & j \ar[u]}

sind für 1 ≤ i ≤ j ≤ n die unzerlegbaren Moduln und

dim_{𝕜} Hom_{𝕜Q}(E_{ij}, E_{kl}) = [E_{ij}, E_{kl}] = \{ \begin{matrix}1 & falls 1 ≤ k ≤ i ≤ l ≤ j ≤ n \\ 0 & sonst \end{matrix}

die Dimensionen der Homomorphismenräume.

Dadurch macht es der Satz von Bongartz leicht zu entscheiden, ob zwei (durch ihre Zerlegung in Unzerlegbare M = ⨁_{i≤j} E_{ij}^{m_{ij}}) gegebene Moduln ineinander entarten.

Ferner existiert eine einfache Beziehung für die Dimensionen der Ext^{1}–Gruppen zwischen Unzerlegbaren, nämlich:

dim_{𝕜} Ext_{𝕜Q}^{1}(E_{ij}, E_{kl}) = \{ \begin{matrix}1 & falls 1 ≤ i < k ≤ j + 1 ≤ l ≤ n \\ 0 & sonst \end{matrix}

Ein weiteres Lemma zur Degenerationsordnung ist das folgende:

Lemma 2.6: (Riedtmann)

Genau dann gilt M ≤_{deg} N, wenn es Zahlen x_{U} ∈ ℕ gibt, wobei U die nicht-projektiv Unzerlegbaren durchläuft, so daß gilt:

N ⊕ ⨁_{U}(B_{U})^{x_{U}} = M ⊕ ⨁_{U}(U ⊕ τ U)^{x_{U}} ,

wobei die direkten Summen über alle U unzerlegbar, nicht-projektiv laufen und

\xymatrix{0 \ar[r] & τ U \ar[r] & B_{U} \ar[r] & U \ar[r] & 0}

die Auslander–Reiten–Sequenz mit Ende U bezeichnet.

Wendet man dieses Lemma auf den Köcher Q = A_{n} an, so erhält man aus einem Modul M = ⨁_{i≤j} E_{ij}^{m_{ij}} alle Entartungen N = ⨁_{i≤j} E_{ij}^{n_{ij}} indem man Zahlen (x_{ij})_{1≤i≤j<n} wählt und

n_{ij} = m_{ij} − x_{i−1,j} − x_{i,j−1} + x_{i−1,j−1} + x_{ij}

setzt (unter der Nebenbedingung, daß alle diese n_{ij} natürlich wieder ≥ 0 sein müssen!).

2.2 Reduktion von ω nach γ

Im zweiten Schritt definiere die Laurent–Polynome γ_{N}^{M} ∈ ℤ[v, v^{−1}] durch

M_{[M]} = ∑_{[N]} γ_{N}^{M}E_{[N]},

wobei die M_{[M]} eine dritte Basis von U_{q}^{+}(sl_{n}), die sogenannte Monomialbasis^{2}, bilden.

Es ist

M_{[M]} = E_{n}^{(a_{nn})}
·E_{n−1}^{(a_{n−1,n−1})} · E_{n}^{(a_{n−1,n})}
·E_{n−2}^{(a_{n−2,n−2})} · E_{n−1}^{(a_{n−2,n−1})} · E_{n}^{(a_{n−2,n})}
⋮
·E_{2}^{(a_{22})} · E_{3}^{(a_{23})} · · · · · E_{n}^{(a_{2n})}
·E_{1}^{(a_{11})} · E_{2}^{(a_{12})} · · · · · E_{n}^{(a_{1n})}
∈ U_{q}^{+}(sl_{n})

2Diese Basis ist für die Struktur von U_{q}^{+}(sl_{n}) eher uninteressant und wird nur in diesem Algorithmus benötigt.

Dokumentation — \begin{matrix}c \\ ◯ \end{matrix} 1998 by 𝔇irk 𝔇udek & Jens Bender 9

Dabei ist

E_{i}^{(r)} = E_{[E_{i}^{r}]}

und die a_{ij}, 1 ≤ i ≤ j ≤ n ergeben sich aus M = ⨁_{i≤j} E_{ij}^{m_{ij}} durch:

a_{ij} = ∑_{k=j}^{n} m_{ik} für alle 1 ≤ i ≤ j ≤ n.

Die Elemente M_{[M]} erfüllen die Bedingung

\overline{M_{[M]}} = M_{[M]}

und es gilt wieder a) γ_{N}^{M} ≠ 0 ⇒ M ≤_{deg} N.

b) γ_{M}^{M} = 1. Daraus läßt sich wieder ein rekursives Berechnungsverfahren ableiten. Lemma 2.7:

Angenommen es sind bekannt

a) Alle Koeffizienten γ_{N}^{M}.

b) Alle Polynome ω_{L}^{M} mit M ≤_{deg} L <_{deg} N. Dann erhält man die Koeffizienten ω_{N}^{M} durch:

ω_{N}^{M} = γ_{N}^{M} − ∑_{L: M<_{deg}L≤_{deg}N} \overline{γ_{L}^{M}} · ω_{N}^{L}.

2.3 Reduktion von γ nach c

Im dritten Schritt definiere die Koeffizienten c_{i}^{r}(M, M_{a}) durch

E_{i}^{(r)} · E_{[M]} = ∑_{a=(a_{i},...,a_{n})} c_{i}^{r}(M, M_{a}) · E_{[M_{a}]}  (1)

für gewisse Moduln M_{a}, die im folgenden Kapitel 2.4 definiert werden. Für einen gegeben Modul M = ⨁_{k≤l} E_{kl}^{m_{kl}} läuft die Summe über alle Tupel (a_{i}, … a_{n}) mit

i) a_{k} ≥ 0 für alle k = i, …, n.

ii) ∑_{k=i}^{n} a_{k} = r. Damit läßt sich das Element M_{[M]}, d.h. alle Koeffizienten γ_{N}^{M}, berechnen, indem man mit dem Eins–Element E_{[0]} der Algebra U_{q}^{+}(sl_{n}) startet und wiederholt mit entsprechenden E_{i}’s von links multipliziert, was bei Kenntnis der c_{i}^{r}(M, M_{a}) explizit möglich ist.

2.4 Berechnung der Koeffizienten c_{i}^{r}(M, M_{a})

Im vierten und letzten Schritt geht das einzig mathematisch Neue vom Algorithmus ein, denn die Koeffizienten c_{i}^{r}(M, M_{a}) waren bislang nicht bekannt.

Satz 2.8:

Schreibe M = ⨁_{k≤l} E_{kl}^{m_{kl}}. Dann gilt:

c_{i}^{r}(M, M_{a}) = v^{∑_{k=i}^{n} a_{k}( ∑_{l=k+1}^{n}(m_{il}−m_{i+1,l}))+∑_{i≤k<l≤n} a_{k}a_{l}}·∏_{k=i}^{n} [{m_{ik} + a_{k} \atop a_{k}} ].

(2)

Hierbei bedeuten:

[s] := \frac{v^{s} − v^{−s}}{v − v^{−1}} = v^{s−1} + v^{s−3} + ⋯ + v^{3−k} + v^{1−k}

[s]! := [1] · [2] · · · · · [s]

[{s + t \atop t}] := \frac{[s + t]!}{[s]! · [t]!}

M_{a} := ⨁_{1≤k≤l≤n} E_{kl}^{m′_{kl}} mit m′_{kl} = \{ \begin{matrix}m_{kl} + a_{l} & falls k = i \\ m_{kl} − a_{l} & falls k = i + 1 \\ m_{kl} & sonst \end{matrix}

Wegen der Beziehung

∑_{i≤k<l≤n} a_{k}a_{l} = ∑_{k=i}^{n} ∑_{l=k+1}^{n} a_{k}a_{l}

läßt sich die Gleichung (2) umschreiben in

c_{i}^{r}(M, M_{a}) = v^{∑_{k=i}^{n} a_{k}( ∑_{l=k+1}^{n}(m_{il}−m_{i+1,l}+a_{l}))} · ∏_{k=i}^{n} [{m_{ik} + a_{k} \atop a_{k}} ].  (3)

Für die Gauss’schen Binomialkoeffizienten ist leider keine explizite Formel als Polynome in ℕ[v, v^{−1}] bekannt. Sie lassen sich jedoch rekursiv durch

[{s \atop t}] = v^{s−t} · [{s − 1 \atop t − 1}] + v^{−t}[{s − 1 \atop t}]

berechnen. Der Abbruch der Rekursion wird geliefert durch

[{s \atop s}] = [{s \atop 0}] = 1.

Liest man die vier Schritte des Algorithmus umgekehrt, so lassen sich die Basiswechsel–Polynome ζ_{N}^{M} durch iteriertes Anwenden der Formel (1) aus dem dritten Schritt auf den Null–Modul und zweimaliges Auflösen einer Rekursion über die Entartungsordnung explizit berechnen.

3 Das Programm

3.1 Anforderungen an das Programm

Als Eingabe sollte das Programm die folgenden Parameter akzeptieren:

a) Die Länge n des Köchers A_{n}.

b) Koeffizienten m_{ij}, 1 ≤ i, j ≤ n, durch welche ein beliebiger 𝕜Q–Modul als Zerlegung in Unzerlegbare M = ⨁_{i≤j} E_{ij}^{m_{ij}} eindeutig festliegt.

Für die so spezifizierte Köcherlänge n und den Modul M soll dann eine Liste von Paaren der Form

N mit M ≤_{deg} N, ζ_{N}^{M}

ausgegeben werden, d.h. jeder Modul N mit M ≤_{deg} N und der zugehörige Basiswechselkoeffizient ζ_{N}^{M}.

Realistische Schranken für die Eingabewerte liegen bei

n ≤ 8  und  dim_{𝕜} M ≤ 20.

Ferner kann die Rechenzeit für Eingaben nahe diesen Schranken im mehrstündigen Bereich liegen, denn bereits für n ≥ 4 sind so gut wie keine nicht-trivialen Beispiele bekannt.

Sowohl die Eingabe der Parameter als auch die Ausgabe der Liste von Paaren dürfen schlicht gehalten werden.

3.2 Wahl der Programmiersprache

Für die Umsetzung des Algorithmus in ein ausführbares Programm kamen die Compiler–Programmiersprache C und die interpretierte Sprache Mathematica in die engere Auswahl. Die Entscheidung fiel aus folgenden Gründen schließlich auf C :

a) Die Programmiersprache C ist stark verbreitet und gehört zu den Sprachen, in denen heutzutage programmiert wird. Daher und durch die universelle Einsetzbarkeit von C wird eine große Portabilität unseres Programms gewährleistet.

Im Gegensatz dazu ist Mathematica zwar an vielen Universitäten vorhanden, aber dort nicht immer allgemein zugänglich oder durch alternative Sprachen wie etwa Maple in ihrer Nutzung beeinträchtigt. Ferner erfordert Mathematica einige Benutzungskenntnisse, was den Einsatzbereich eines in dieser Sprache geschriebenen Programms zusätzlich eingeschränkt. b) Aus der mathematischen Beschreibung des Algorithmus ist sofort ersicht-

lich, daß dieser eine Vielzahl an Rechenoperationen mit Polynomen und insbesondere Laurent–Polynomen umfaßt. Zur Handhabung der Polynome stellt Mathematica eine ganze Reihe von bequemen Funktionen und Operationen (Polynomdivision, Laurent–Reihen, Binomialkoeffizienten, ...) zur Verfügung. Diese würden es z.B. erlauben die rekursive Berechnung der Gauss’schen Binomialkoeffizienten zu vermeiden. Die Arithmetik mit Polynomen muß in C zwar erst programmiert werden, aber dieser zusätzliche Aufwand ist gering. Auch die Verwaltung der Polynome erfordern keine größeren Umstände.

c) Nahe der Parameter–Eingabeschranken wird der Speicherbedarf und der Rechenaufwand verhältnismäßig groß, so daß der Zeitaufwand bei einem auf Mathematica basierenden Programm erheblich höher ist als bei einem vergleichbaren C –Programm (Interpreter ↔ Compiler). Insbesondere werden wohl die zum Teil tiefgehenden Rekursionen über die Degenerationsordnung mit einem C –orientierten Programm schneller abgearbeitet als durch Mathematica–Programme.

Die Wahl der Programmiersprache C begründet sich also hauptsächlich durch die große Portabilität und der besseren Rechengeschwindigkeit von C gegenüber Mathematica, die durch wenige Zusatzprozeduren (Arithmetik mit Polynomen) nicht gemindert wird.

Als Compiler wurde der GNU–C–Compiler gewählt, der auf praktisch allen Plattformen zur Verfügung steht. Das Programm nutzt einige Besonderheiten dieses Compilers ([0]–Arrays, inline–Funktionen), was aber die Portabilität nicht einschränkt.

3.3 Aufruf und Benutzung

Die Aufrufschablone des Programms lautet

kristallin [--test] [--all] [--verbose] [--debug] [--logmem]

Dabei bedeuten die einzelnen Optionen:

--test Die in Abschnitt 3.4 aufgeführten Tests werden durchgeführt. Schlägt einer der Tests fehl, wird der Text ”Programm buggy“ auf stderr ausgegeben und das Programm wechselt in den --debug-Modus. Natürlich verlangsamt diese Option den Programmlauf etwas.

--all Nach Start des Programms wird als erstes die Länge des zu behandelnden Köchers erfragt, danach der zu betrachtende Dimensionsvektor. Wird diese Option nicht angegeben, wird anschließend der zu betrachtende Modul gegeben durch seine Zerlegung in Unzerlegbare eingegeben. Wird diese Option aber angegeben, werden nacheinander alle Moduln, die zum gegebenen Dimensionsvektor passen, behandelt. Diese Option eignet sich besonders, um einen gewissen Überblick zu bekommen und um die Testläufe ökonomischer durchführen zu können.

--verbose Zusätzlich zu den ζ_{N}^{M} werden auch alle benötigten ω_{N}^{M} und γ_{N}^{M} ausgegeben. Weiterhin werden vor der Eingabe des Moduls alle Unzerlegbaren und alle Moduln zum gegebenen Dimensionsvektor ausgegeben. Die Moduln werden dabei durch eine Kurzschreibweise dargestellt, und zwar werden die Multiplizitäten der Unzerlegbaren in der Reihenfolge E_{1,n}, E_{1,n−1}, E_{2,n}, E_{1,n−2}, …, E_{11}, …, E_{nn} ausgegeben (n ist die Länge des Köchers).

--debug Zusätzlich zu --verbose wird die Berechnung der M_{[M]} ausführlich angezeigt, einschließlich aller c_{i}^{r}(M, M_{a}).

--logmem Der maximal benutzte Speicher für diesen Programmlauf wird angezeigt. Ebenso wie --test wird das Programm etwas verlangsamt, außerdem wird der Speicherverbrauch etwas erhöht. Dieser zusätzliche Speicherverbrauch wird aber nicht mitgerechnet, ebenso bleibt der durch malloc eingebrachte Overhead unberücksichtigt.

Bei der Eingabe der Moduln als direkte Summe der Unzerlegbaren ist zu beachten, daß nur die Multiplitzitäten der Unzerlegbaren abgefragt werden, die noch nicht eindeutig durch vorhergehende Eingaben und den Dimensionsvektor festgelegt sind. Die Eingaben müssen im bei der Eingabeaufforderung angegebenen Bereich liegen, damit sie akzeptiert werden.

3.4 Tests

Die Theorie der Quantengruppen und der Köcheralgebren liefert mehrere, einfach zu überprüfende Tests für das Programm. Zu diesen Tests zählen:

a) Für die Koeffizienten c_{i}^{r}(M, M_{a}) gilt:

E_{i}^{(r)} · E_{[M]} = c_{i}^{r}(M, M_{a}) · E_{[M⊕E_{i}^{r}]} falls Ext_{𝕜Q}^{1}(E_{i}^{r}, M) = 0.

Die Bedingung Ext_{𝕜Q}^{1}(E_{i}^{r}, M) = 0 läßt sich leicht für einen gegeben Modul M = ⨁_{k≤l} E_{kl}^{m_{kl}} durch

m_{i+i,l} = 0 für alle l = i + 1, …, n

überprüfen.

b) Ein weiteres Kriterium für die c_{i}^{r}(M, M_{a})–Koeffizienten ergibt sich aus:

E_{i}^{(r)} · E_{[M]} = ∑_{a=(a_{i},...,a_{n})} v^{α} · E_{[M_{a}]} falls Hom_{𝕜Q}(M, E_{i}) = 0,

wobei α ∈ ℤ. Für einen Modul M = ⨁_{k≤l} E_{kl}^{m_{kl}} gilt dabei:

Hom_{𝕜Q}(M, E_{i}) = 0 ⇔ m_{il} = 0 für alle l = i, …, n.

c) Bei der Berechnung der ζ–Koeffizienten muß die folgende Bedingung erfüllt

sein:

E_{[M]} = E_{1}^{(d_{1})} ⋯ E_{n}^{(d_{n})} = ∑_{N: \underline{dim} N=d} \underbrace{v^{− dim Ext^{1}(N,N)}}_{=ζ_{N}^{M}} ·E_{[N]}.

Dabei ist vorausgesetzt:

Ext_{𝕜Q}^{1}(M, M) = 0  und  \underline{dim} M = d.

d) Der wirksamste Test überhaupt ist die Überprüfung der ζ–Koeffizienten gemäß Satz 1.3 nach Lusztig:

v^{[N,N]−[M,M]} · ζ_{N}^{M} ∈ ℕ[v^{2}],

da die Positivität der Polynom–Koeffizienten mit tiefliegenden Methoden der algebraischen Geometrie bewiesen worden ist.

Alle obigen Tests sind mit ins Programm eingebaut und werden bei aktivierter Option --test automatisch durchlaufen.

Insbesondere für den Köcher A_{2} sind explizite Formeln bekannt, die im Vorfeld nachgerechnet wurden und mit der Programmausgabe übereinstimmen.

3.5 Umsetzung des Algorithmus in Programmtext

Der Algorithmus wurde wie im Theorieteil (Kapitel 2) geschildert umgesetzt. Dabei sind dem Programm einige erklärende Kommentare als Programmtext hinzugefügt worden, um wichtige Programmdetails zu beleuchten.

Das Programm besitzt keine Schranken für die Eingabeparameter, wie sie in Kapitel 3.1 angegeben sind. Praktisch sind beliebig hohe Werte für Köcherlänge und Modul–Dimension möglich. Doch die protokollierten Testläufe machen deutlich, daß große Eingabewerte hohen Speicherplatzbedarf fordern und die Geduld des Programmnutzers auf die Probe stellen.

3.6 Probeläufe

Die Probeläufe wurden auf der SGI–Workstation O_{2} mit einem MIPS R5000 Prozessor (180 MHz Taktfrequenz) und 160 MB RAM durchgeführt. Dabei waren stets die Optionen --all --test --logmem aktiviert und die Ausgabe direkt auf dem Bildschirm präsentiert (also ohne Ausgabeumlenkung).

In der folgenden Tabelle sind einige der Probeläufe protokolliert:

Dimensionsvektor  Anzahl  Speicherverbrauch Rechenzeit
der Moduln  in [kB]  in [s]
2–2  3  1  < 1
1–2–2  7  3  < 1
2–2–2  10  6  < 1
2–2–2–2  35  60  1
1–2–3–4  40  105  < 1
2–2–3–3  56  182  1
3–3–3–3  112  811  5
4–4–4–4  294  7306  104
2–2–2–2–2  125  647  5
2–2–2–2–2–2  450  7058  90
2–2–2–2–2–2–2  2625  77752  1740

Sowohl die Rechenzeit als auch der Speicheraufwand werden erheblich geringer, wenn die Option --all nicht benutzt wird, sondern einzelne Moduln berechnet werden.

Es sei schließlich noch erwähnt, daß während aller Probeläufe die Option --test keine Fehlermeldung produzierte!