Ganzzahlige Optimierungsmodelle für Subspace Codes und endliche Geometrie

• Antragsteller: Privatdozent Dr. Sascha Kurz; Professor Dr. Alfred Wassermann
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2015 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 266952998

Fehlerkorrigierende Codes werden heute in nahezu jeder Form der Informationsübertragung und -speicherung eingesetzt. Prominente Beispiele sind Kommunikation mit Weltraumsonden, Digitales Fernsehen (DVB), ADSL, verteilte Speichersysteme (Windows Azure) und CD-Player. Vielfältige Anwendungen in Kommunikationsnetzen wie dem Internet, mobilen Endgeräten wie Smartphones und Cloud Computing, erfordern eine mathematische Theorie, die unabhängig von der Netzwerktopologie ist. Erst vor wenigen Jahren wurde erkannt, dass die Durchsatzraten in bestimmten Situationen noch deutlich verbessert werden können, indem Datenpakete überlagert werden, d.h. über einem geeigneten endlichen Körper linear kombiniert werden. Wenn in diesem Kommunikationsmodell auch Fehler korrigiert werden sollen, bietet es sich an, als Alphabet die Menge aller Teilräume eines endlichen Vektorraumes zu betrachten. Ein subspace code ist dann eine Menge geeigneter Teilräume. Eine Hauptforschungsrichtung ist die Existenzfrage und die Konstruktion von guten bzw. optimalen subspace codes. Dieses Problem ist hochaktuell und beispielsweise Thema der EU COST Action IC1104. Eine umfassende Suche nach guten subspace codes wird erschwert durch die Tatsache, dass die Anzahl aller Teilräume eines endlichen Vektorraumes und die Größe der zugehörigen Automorphismengruppe schon für kleine Parameter sehr groß wird. In Bayreuth wurden in den letzten Jahren computerunterstützte Konstruktionsverfahren in verschiedenen Gebieten der diskreten Mathematik sehr erfolgreich eingesetzt. Die zugrunde liegende Idee hierbei ist, den Suchraum mit Methoden der Gruppentheorie zu verkleinern. Entweder sucht man nur Lösungen mit vorgegebenen Symmetrien oder nutzt die Isomorphie zwischen unterschiedlichen Lösungen aus. Die Suche nach Inzidenzstrukturen lässt sich auf die Lösung eines ganzzahligen linearen Gleichungssystems zurückführen. Im Rahmen dieses Projektes wird ein derartiger Ansatz auf die vorliegende Fragestellung angepasst. Als Innovation sollen mit Hilfe theoretischer Resultate aus der endlichen Geometrie und durch Betrachtung von Schnittzahlen schärfere ganzzahlige Formulierungen gefunden werden. Grundidee hierbei ist, geeignete geometrische Teilstrukturen zu modellieren, zu klassifizieren und als Restriktion dem ursprünglichen Problem hinzuzufügen. Das in "T. Honold, M. Kiermaier, and S. Kurz. Optimal binary subspace codes of length 6, constant dimension 3 and minimum distance 4. 2014. to appear in the Proceedings of Fq 11" beschriebene Vorgehen zur Klassifikation von sogenannten (6,3,4)_2 constant-dimension codes ist hier exemplarisch für den neuen strategischen Ansatz (siehe Anhang). Da es im Bereich der subspace codes nur sehr wenige moderate Parametersätze gibt, ist es gerechtfertigt, für jeden von diesen einen größeren Aufwand zu betreiben. Gleichwohl sollen systematisch alle kleineren Fälle untersucht werden. Auch die Verbesserung von Schranken ist in manchen Fällen schon ein Fortschritt.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: China
• Kooperationspartner: Professor Dr. Michael Braun; Professor Dr. Thomas Honold