Problemstellung und Stand der Forschung

Problemstellung und Stand der Forschung

1. Sei G eine endliche Gruppe und sei X eine endliche Menge, dann ist eine endliche Gruppenaktion _GX durch die folgende Abbildung gegeben.

   G´X -> X        (g,x) -> gx,

   mit g₁(g₂x)=(g₁g₂)x und 1x=x für alle g₁,g₂ ÎG und xÎX, wobei 1 das neutrale Element in G ist. So wie das Lemma von Burnside bei Gruppenaktionen _GX jetzt formuliert ist, benötigt man den gesamten Untergruppenverband der operierenden Gruppe G, um die Mächtigkeiten der U-Strata [~ ] U\\\X:={G(x) | G_xÎ[~U] } zu berechnen. Dabei und im folgenden wird folgende Notation verwendet, wobei vorausgestzt wird, daß xÎX, gÎG, und U eine Untergruppe von G ist:

   G(x):={gx | gÎG}     G_x:={gÎG | gx=x}

   [~U] :={gUg^-1 | gÎG}

   X_g:={xÎX | gx=x}     X_U:=Ç_gÎU X_g

   (Lemma von Burnside)    [16] (3.1.4 Burnside's Lemma)    Sei _GX eine endliche Gruppenaktion und seien [~U] ₁,..., [~U] _d die Konjugiertenklassen von Untergruppen von G mit Repräsentanten U_iÎ [~U] _i. Dann gilt wobei die Burnsidematrix  B(G):=(b_ik(G))_{1£i, k£ d}definiert ist durch

   b_ik(G):=(| [~U] _i| )/(| G/U_i| )å_{VÎ [~U] k}m(U_i,V)= (| [~U] _k| )/(| G/U_i| )å_{VÎ[~U] i}m (V,U_k).

   (Dabei ist m die m-Funktion in der Inzidenzalgebra über den Untergruppenverband L(G):={U | U£G} von G.) Tatsächlich kommen nur gewisse Untergruppen U£G als Stabilisatoren von Elementen xÎX in Frage. Kann man eine Formulierung des Lemmas von Burnside finden, in der diese Tatsache berücksichtigt wird? G.-C. Rota und A. Smith haben in Ihrer Arbeit "Enumeration Under Group Action" (1977) [27] erste Versuche unternommen, nur mit solchen Untergruppen zu rechnen, die als Stabilisatoren auftreten können.
2. Weiters sollen Konstruktionsverfahren von Orbitrepräsentanten in _G(Y^X) genauer untersucht werden, wobei die operierende Gruppe G das direkte Produkt zweier Gruppen ist, von denen die eine von rechts, die andere von links auf Y^X, der Menge aller Abbildungen von X nach Y, operiert. In der Diktion der Dissertation von Herrn Fripertinger ist das die de Bruijn-Situation. Bisher wurden hauptsächlich Konstruktionsverfahren von Orbitrepräsentanten in _G(Y^X) untersucht, wobei G nur auf der Menge X ( Pólya-Situation) oder G durch Konjugieren "simultan" von links und rechts operiert. In diesem Zusammenhang spielen Sims-Ketten eine entscheidende Rolle. Man definiert auf der Menge Y^X eine lineare Ordnung, und sucht in jedem Orbit den - bezüglich dieser Ordnung - kleinsten Vertreter. (Dieses Verfahren bezeichnet man als den Minimalitätstest für fÎY^X.) Um auf vernünftige Weise Repräsentantenlisten erstellen zu können, versucht man diesen Minimalitätstest - durch geschickte Anordnung der Gruppenelemente und entsprechende Auswertung der Größenverhältnisse zwischen f und f o g - möglichst stark abzukürzen.
3. Neben der vollständigen Auflistung von Orbit-Repräsentanten gibt es auch Verfahren zur zufälligen, über alle Orbiten gleichverteilten Repräsentantenkonstruktion. Bisher hatte Herr Fripertinger ein Programm zur zufälligen Erzeugung von Lyndon-Wörtern geschrieben. (Es läuft unter Verwendung von Routinen des Programmsystems SYMMETRICA auf einer Workstation.) Dieses Programm stellt eine Anwendung des Satzes von Laue, (siehe [19]) bzw. des Dixon-Wilf-Algorithmus zur zufälligen Konstruktion von Orbit-Repräsentanten zu gegebenem Stabilisatortyp (siehe [16] [5][7][6]) dar. In diesem Zusammenhang tritt die zyklische Gruppe als operierende Gruppe auf. Lyndon-Wörter kommen in verschiedensten Bereichen der Mathematik vor. So entsprechen ihnen z.B. die irreduziblen normierten Polynome über Galoisfeldern, oder sie treten als Basen in Lie-Algebren auf. Es wäre interessant, diesen Algorithmus auch bei Gruppenaktionen anderer Gruppen einzusetzen. Dabei werden Ergebnisse aus 1. gut anwendbar sein. Weiters kann man mit verschiedenen statistischen Methoden untersuchen, wann man aus jedem Orbit von vorgegebenem Typ einen Repräsentanten errechnet hat. Wieviele Objekte muß man durchschnittlich erzeugen, bis man aus jedem Orbit mindestens einen Vertreter aufgelistet hat? Mit dieser Methode steht dann ein generelles Verfahren zur Verfügung, um diskrete Strukturen zufällig, gleichverteilt, vorurteilsfrei zu erzeugen. Damit ist es möglich, große Beispielssätze sehr schnell zu generieren, und es besteht die Möglichkeit, Hypothesen über endliche Strukturen zu überprüfen (z.B. Trennfähigkeit von Invarianten oder andere Vermutungen).
4. Auf dem Gebiet der mathematischen Musiktheorie hat Herr Fripertinger den Satz von Pólya und mit diesem verwandte Theoreme verwendet, um die Anzahlen "wesentlich verschiedener" Objekte wie Intervalle, Akkorde, Tonreihen, Motive, Tropen usw. in n-Tonmusik zun bestimmen. Siehe zum Beispiel [8]. Des weiteren ist eine Publikation mit Herrn Mazzola geplant. Im Rahmen seiner Dissertation hat Herr Fripertinger sich mit Anwendungen der unter 2. und 3. vorgestellten Konstruktionsmethoden zur Erstellung von Motivklassifikationslisten von Motiven in einem 12-Takt in 12-Tonmusik beschäftigt. Ein k-Motiv in einem n-Takt in m-Tonmusik ist eine k-elementige Teilmenge von Z_n´Z_m. (Z_n sei die Menge der Restklassen Z/nZ.) Zwei k-Motive mögen äquivalent heißen, falls es eine affine Abbildung in Z_n´Z_m gibt, die ein Motiv auf das andere abbildet. Im Fall n=m=12 ergeben sich folgende Anzahlen von verschiedenen k-Motiv-Repräsentanten: (Es sind nur die Werte für 1£k£20 aufgelistet.)

   k	Anzahl von k-Motiv-Repräsentanten
   1	1
   2	5
   3	26
   4	216
   5	2024
   6	27806
   7	417209
   8	6345735
   9	90590713
   10	1190322956
   11	14303835837
   12	157430569051
   13	1592645620686
   14	14873235105552
   15	128762751824308
   16	1037532923086353
   17	7809413514931644
   18	55089365597956206
   19	365290003947963446
   20	2282919558918081919

   Herr Mazzola kannte bisher nur Repräsentantenlisten für 1£k£4. Siehe [20]. Im Rahmen seiner Dissertation hat Herr Fripertinger solche Listen für 1£k£8 erstellt. Nun sollen solche Listen auch für Takte mit 3, 4, 5, 6, 7, 8, 9, 10 und 16 Einsatzzeiten bestimmt werden, und die Stabilisatoren der Motivrepräsentanten berechnet werden. Für die Bestimmung der Anzahl verschiedener Repräsentanten von k-Motiven muß man den Zyklenzeiger (bzw. Zykelindex) der operierenden Gruppe bestimmen. Dies ist für Gruppen wie Gl(n,Z_k) oder Aff(n,Z_k) ein ziemlich umfangreiches Unterfangen, wie man es vielleicht am Zyklenzeiger von Aff(2,Z₁₂) bereits erkennen kann:

   Z(Aff(2,Z₁₂);x₁,x₂,...,x₁₄₄)=

   =(1)/(663552)( x₁¹⁴⁴ + 18 x₁⁷² x₂³⁶ + 36 x₁⁴⁸ x₂⁴⁸ + 24 x₁⁴⁸ x₃³² + 72 x₁³⁶ x₂⁵⁴ + 48 x₁³⁶ x₂ ¹⁸ x₄¹⁸ + 648 x₁²⁴ x₂⁶⁰ + 432 x₁²⁴ x₂¹² x₃¹⁶ x₆⁸ + 192 x₁¹⁸ x₂⁹ x₄²⁷ + 9 x₁ ¹⁶ x₂⁶⁴ + 72 x₁¹⁶ x₂¹⁶ x₆¹⁶ + 54 x₁¹⁶ x₄³² + 108 x₁¹⁶ x₈¹⁶ + 2592 x₁¹² x₂⁶⁶ + 1728 x₁¹² x₂³⁰ x₄¹⁸ + 1728 x₁¹² x₂¹⁸ x₃⁸ x₆¹² + 1152 x₁¹² x₂⁶ x₃⁸ x₄⁶ x₆⁴ x₁₂⁴ + 128 x₁⁹ x₃⁴⁵ + 384 x₁⁹ x₃⁹ x₆¹⁸ + 162 x₁⁸ x₂⁶⁸ + 1296 x₁⁸ x₂²⁰ x₆ ¹⁶ + 972 x₁⁸ x₂⁴ x₄³² + 1944 x₁⁸ x₂⁴ x₈¹⁶ + 6912 x₁⁶ x₂¹⁵ x₄²⁷ + 4608 x₁⁶ x₂³ x₃⁴ x₄⁹ x₆² x₁₂⁶ + 648 x₁⁴ x₂⁷⁰ + 432 x₁⁴ x₂³⁴ x₄¹⁸ + 5184 x₁⁴ x₂²² x₆¹⁶ + 3456 x₁⁴ x₂¹⁰ x₄⁶ x₆⁸ x₁₂⁴ + 3888 x₁⁴ x₂⁶ x₄³² + 7776 x₁⁴ x₂⁶ x₈¹⁶ + 2592 x₁⁴ x₂² x₄³⁴ + 5184 x₁⁴ x₂² x₄² x₈¹⁶ + 4608 x₁³ x₂³ x₃¹⁵ x₆¹⁵ + 13824 x₁³ x₂³ x₃³ x₆²¹ + 3072 x₁³ x₃⁴⁷ + 9216 x₁³ x₃¹¹ x₆¹⁸ + 1728 x₁² x₂¹⁷ x₄²⁷ + 13824 x₁² x₂⁵ x₄⁹ x₆⁴ x₁₂⁶ + 10368 x₁² x₂ x₄³⁵ + 20736 x₁² x₂ x₄³ x₈¹⁶ + 1152 x₁ x₂⁴ x₃⁵ x₆²⁰ + 3456 x₁ x₂⁴ x₃ x₆²² + 9216 x₁ x₂ x₃⁵ x₆²¹ + 27648 x₁ x₂ x₃ x₆²³ + 6912 x₁ x₃⁵ x₄² x₁₂¹⁰ + 13824 x₁ x₃⁵ x₈ x₂₄⁵ + 20736 x₁ x₃ x₄ ² x₆² x₁₂¹⁰ + 41472 x₁ x₃ x₆² x₈ x₂₄⁵ + 3174 x₂⁷² + 2208 x₂³⁶ x₄¹⁸ + 6624 x₂²⁴ x₆¹⁶ + 4608 x₂¹² x₄⁶ x₆⁸ x₁₂⁴ + 3726 x₂⁸ x₄³² + 7452 x₂⁸ x₈¹⁶ + 2592 x₂⁴ x₄³⁴ + 5184 x₂⁴ x₄² x₈¹⁶ + 7224 x₃⁴⁸ + 1008 x₃²⁴ x₆¹² + 9288 x₃¹⁶ x₆¹⁶ + 25536 x₃¹² x₆¹⁸ + 2688 x₃¹² x₆⁶ x₁₂⁶ + 1296 x₃⁸ x₆²⁰ + 10752 x₃⁶ x₆³ x₁₂⁹ + 32832 x₃⁴ x₆²² + 3456 x₃⁴ x₆¹⁰ x₁₂⁶ + 13824 x₃² x₆⁵ x₁₂⁹ + 38400 x₄³⁶ + 36864 x₄¹² x₁₂⁸ + 41472 x₄⁴ x₈¹⁶ + 8832 x₆²⁴ + 6144 x₆¹² x₁₂⁶ + 39936 x₈¹⁸ + 18432 x₈⁶ x₂₄⁴ + 49152 x₁₂¹² + 24576 x₂₄⁶ ). Im Fall von Gl(n,Z₂) oder Aff(n,Z₂) konnte man in [12] die Zyklenzeiger mit Hilfe von theoretischen Überlegungen wesentlich geschickter bestimmen. Es wäre nun zu untersuchen, wie weit sich diese Verfahren verallgemeinern lassen.
5. Ein weiteres interessantes Forschungsgebiet sind Gruppenaktionen auf POSETs. (Das sind partiell geordnete endliche Mengen.) (Siehe W. Plesken: "Counting with groups and rings" i[21][16].) Nach Vorgabe einer Ordnungsrelation auf einer endlichen Menge und einer Gruppenaktion auf dieser Menge sollte ein Computerprogramm feststellen können, ob diese Ordnungsrelation mit der Gruppenaktion verträglich ist und in diesem Fall verschiedenste Daten (wie z.B. die Matrizen A^Ú und A^Ù) berechnen. Sei (L,Ù,Ú) ein Verband, _GL eine endliche Gruppenaktion, die verträglich mit der Verbandsstruktur ist, und seien w_iÎG\\L die G-Orbiten von L, dann kann man die Matrizen A^Ú:=(a_ik^Ú) und A^Ù:=(a_ik^Ù) definieren durch

   a_ik^Ù:=|{x'Îw_k | x£x'} | und a_ik^Ú:= |{x'Îw_k | x³x'} |,

   wobei xÎw_i beliebig aber fest gewählt ist. Für die Gruppenaktion der Konjugiertenbildung auf dem Untergruppenverband einer endlichen Gruppe G gibt es interessante Zusammenhänge zwischen diesen Matrizen und der Markentafel M(G), die die inverse Matrix zur Burnsidematrix B(G) ist.
6. Schließlich sollte die Literatur auf mögliche Anwendungen des Lemmas von Burnside bei Gruppenaktionen auf Funktionenmengen, das von Herrn Fripertinger in seiner Dissertation formuliert und bewiesen wurde, in den Naturwissenschaften genauer untersucht werden. (Lemma von Burnside)    Seien _GX und _GY zwei endliche Gruppenaktionen. Weiters seien [~U] ₁, ...,[~U] _d alle Konjugiertenklassen von Untergruppen von G mit Repräsentanten U_iÎ[~U] _i. Die U_i-Konjugiertenklassen der Untergruppen von U_i seien mit [~V] _i,1,...,[~V] _i,d(i)bezeichnet mit Repräsentanten V_i,jÎ[~V] _i,j. Unter der Gruppenaktion

   G´Y^X -> Y^X        (g,f) -> g o f o g^-1

   gilt für i=1,...,d

   | [~U] _i\\\Y^X| =å_j=1^db_ij(G)Õ _k=1^d(j)| Y_Vj,k| ^{| [~V] _j,k\\\X|} =

   = å_j=1^db_ij (G)Õ_k=1^d(j)( å _l=1^d(j)m_kl(U_j)| [~V] _j,l\\\Y| ) ^{| [~V] _j,k\\\X|},

   wobei (b_ij(G))_1£i,j£d die Burnsidematrix von G ist, und (m_kl(U_j))_1£k,l£d(j) die Markentafel von U_j ist.
7. Herr Kerber hat Herrn Fripertinger im Zusammenhang mit der algebraischen Kombinatorik auf die Theorie der " Interaction Models" von N. L. Biggs [1] hingewiesen. Es könnten sich einige interessante Ergebnisse in Verbindung mit seiner Dissertation ergeben.
8. Weiters sollte die Redfieldsche Abzähltheorie [25] genauer untersucht werden. Vielleicht ist es möglich, so wie dies bei der Pólyaschen Abzähltheorie geschehen ist, auch diese Theorie durch Hinzunahme von darstellungstheoretischen Hilfsmitteln zu verallgemeinern. Obwohl diese Theorie bereits vor der Pólyaschen Abzähltheorie entwi"ckelt wurde, ist sie doch noch relativ unbekannt. A. Smith hat einen Artikel über eine Anwendung der Redfield-Theorie in der Chemie geschrieben. Die beiden von Redfield eingeführten Operatoren (cup- und cap-Operator) sollten in dem Programmsystem SYMMETRICA eingebaut werden.
9. Darüber hinaus gibt es das Forschungsgebiet der sogenannten Postfunktionen, auf das Herr Kerber auch aufmerksam gemacht hat. Eine Postfunktion ist eine Abbildung f von Z_mⁿ nach Z_m. Siehe [13][24]. Auf der Menge aller Postfunktionen untersucht man verschiedenste Gruppenoperationen, und versucht die Anzahlen der Orbiten von solchen Funktionen zu berechnen oder Repräsentantenlisten zu erstellen.
10. Weiters sei auch auf die Species-Theorie hingewiesen. Die erste bedeutende Arbeit auf diesem Gebiet war [14]. In der Zwischenzeit wurde diese Theorie hauptsächlich in Canada weiterentwickelt. All die Ergebnisse dieser Theorie sollten als konstruktive Species-Theorie in einem Programmpaket wie z.B. SYMMETRICA implementiert werden. Dieses Vorhaben dürfte jedoch den zeitlich gesetzten Rahmen bei weitem sprengen. Bei der konstruktiven Species-Theorie geht es darum, neuen Datentyp "Species" zu implementieren. Damit soll es möglich sein, alle üblichen Beispiele von Species zu modellieren. Weiters müssen Verknüpfungen zwischen Species erklärt werden, sodaß man aus gegebenen Species weitere konstruieren kann. Für die Abzähltheorie der Species benötigt man dann Zykelindexreihen. Bei der Species-Theorie gibt es auch Verbindungen zur Analysis, so gibt es einige Beiträge über kombinatorische Differentialgleichungen ( G. Labelle: "On Combinatorial Differential Equations" [18]).
11. Neben diesen Vorhaben wäre es auch von großem Interesse, eine Aufstellung aller Publikationen, das Gebiet der Pólya-Theorie betreffend, anzulegen.

Darstellungstheorie endlicher Gruppen und die Algebraische Kombinatorik. Herr Mazzola ist ein bedeutender Vertreter der Mathematischen Musiktheorie. Sein Buch "Geometrie der Töne" [20] stellt einen guten Gesamtüberblick über den Stand der Forschung dar. Herr Fripertinger hat über Konstruktionsverfahren für Motivrepräsentanten in Zürich bereits einen Vortrag gehalten.

---

harald.fripertinger@kfunigraz.ac.at,
last changed: January 28, 2002

Problemstellung und Stand der Forschung