Integer Linear Programming Models for Subspace Codes and Finite Geomery
Final Report Abstract
Fehlerkorrigierende Codes werden seit Jahrzehnten in nahezu jeder Form der Informationsübertragung und -speicherung eingesetzt. Prominente Beispiele sind Kommunikation mit Weltraumsonden, Digitales Fernsehen (DVB), ADSL, Festplatten, Flashspeicher, verteilte Speichersysteme und CD-Player. Vielfältige Anwendungen in Kommunikationsnetzen wie dem Internet, mobilen Endgeräten wie Smartphones und Cloud Computing, mit ihren schnell wechselnden technischen Standards, erfordern eine mathematische Theorie, die unabhängig von der genauen Netzwerktopologie ist. Bislang werden die Durchsatzraten in diesen Kommunikationsnetzen durch ausgeklügelte Routing-Strategien optimiert. 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. Sollen in diesem Kommunikationsmodell auch Fehler korrigiert werden, so bietet es sich ganz natürlich an, fehlerkorrigierenden Codes als Alphabet die Menge aller Teilräume eines endlichen Vektorraums zugrunde zu legen. Denn Teilräume sind invariant gegenüber Linearkombinationen ihrer Vektoren. Der Abstand zweier Teilräume (subspace distance) wird als die Länge des kürzesten Wegs im Teilraumverband festgelegt. Ein Subspace-Code besteht dann aus einer Menge geeigneter Teilräume. Von besonderer Bedeutung sind Codes bei denen alle Teilräume die gleiche Dimension haben, die so genannten Constant-Dimension-Codes. Im Zentrum der Forschung steht die Existenzfrage und die Konstruktion von guten bzw. optimalen Subspace-Codes, d.h. Subspace-Codes mit möglichst großer Kardinalität bei gegebener Umgebungsraumdimension und Minimaldistanz. Eine umfassende Suche nach guten Subspace-Codes und Constant-Dimension-Codes wird durch die Tatsache erschwert, dass die Anzahl aller Teilräume eines endlichen Vektorraumes schon für kleine Parameter sehr groß ist. Die auf diesen Objekten operierende Symmetriegruppe ist in der Regel ebenfalls riesig und verursacht weitere algorithmische Herausforderungen. Die Frage, wie groß Constant-Dimension-Codes für gegebene Parameter maximal sein können, war vor dem Projekt nur in zwei nichttrivialen Fällen mit nicht maximaler Distanz geklärt und nur in einem dieser beiden Fälle waren alle maximalen Constant- Dimension-Codes bekannt. Eines der Hauptresultate dieses Projektes ist die Klassifikation der maximalen Codes eines weiteren Parametersatzes. Im momentan wichtigsten offenen Fall – dem der binären Fano-Ebene – konnten wir einen neuen größten Constant-Dimension-Code konstruieren. Um dieses Ergebnis zu ermöglichen, wurden zuerst diejenigen Symmetriegruppen von Constant-Dimension-Codes klassifiziert, die große Code-Kardinalitäten für die gewünschten Parameter ermöglichen. In einem zweiten Schritt konnte ein so gefundener Code dann auf Rekordgröße erweitert werden. In der Existenzfrage für die binäre Fano-Ebene konnten wir zeigen, dass sie, falls sie überhaupt existiert, höchstens eine nichttriviale Symmetrie haben kann. Darüberhinaus wurden in diesem Projekt zahlreiche Schranken an die Kardinalitäten der besten Codes verbessert und neue Konstruktionen für Constant-Dimension-Codes entwickelt. Zum Beispiel liefert die neue improved linkage construction häufig die besten bekannten Codes. Um die Ergebnisse zu sichern und der Allgemeinheit zur Verfügung zu stellen wurde im Verlauf des Projektes eine Online-Datenbank erstellt, die das Wissen zu Subspace-Codes und Constant-Dimension-Codes sammelt, vergleicht und auflistet.
Publications
- Asymptotic bounds for the sizes of constant dimension codes and an improved lower bound. In Ángela I. Barbero, Vitaly Skachek, and Øyvind Ytrehus, editors, Coding Theory and Applications: 5th International Castle Meeting, ICMCTA 2017, Vihula, Estonia, August 28-31, 2017, Proceedings, volume 10495 of Lecture Notes in Computer Science, pages 163–191, 2017
D. Heinlein and S. Kurz
(See online at https://doi.org/10.1007/978-3-319-66278-7_15) - Coset construction for subspace codes. IEEE Transactions on Information Theory, 63(12):7651–7660, 2017
D. Heinlein and S. Kurz
(See online at https://doi.org/10.1109/TIT.2017.2753822) - Packing vector spaces into vector spaces. The Australasian Journal of Combinatorics, 68(1):122–130, 2017
S. Kurz
- Binary Subspace Codes in Small Ambient Spaces. Advances in Mathematics of Communications, 12(4):817–839, 2018
D. Heinlein and S. Kurz
(See online at https://doi.org/10.3934/amc.2018048) - Partial spreads and vector space partitions. in Network Coding and Subspace Designs, Eds. M. Greferath, M.O. Pavčević, N. Silberstein, and A. Vazquez-Castro, Springer, 131–170, 2018
T. Honold, M. Kiermaier, and S. Kurz
(See online at https://doi.org/10.1007/978-3-319-70293-3_7) - The order of the automorphism group of a binary q-analog of the Fano plane is at most two. Designs, Codes and Cryptography, 86(2): 239–250, 2018
M. Kiermaier, S. Kurz, and A. Wassermann
(See online at https://doi.org/10.1007/s10623-017-0360-6) - (2019): 2. q-analogs of group divisible designs. In: Kai-Uwe Schmidt und Arne Winterhof (Hg.): Combinatorics and Finite Fields: De Gruyter, S. 21–38.
M. Buratti, M. Kiermaier, S. Kurz, A. Nakić, and A. Wassermann
(See online at https://doi.org/10.1515/9783110642094-002) - Classifying optimal binary subspace codes of length 8, constant dimension 4 and minimum distance 6. Designs, Codes and Cryptography
D. Heinlein, T. Honold, M. Kiermaier, S. Kurz, and A. Wassermann
(See online at https://doi.org/10.1007/s10623-018-0544-8) - Classification of large partial plane spreads in P G(6, 2) and related combinatorial objects. Journal of Geometry, 110(5):1–31, 2019
T. Honold, M. Kiermaier, and S. Kurz
(See online at https://doi.org/10.1007/s00022-018-0459-6)
