EINE VERMUTUNG VON 1969 ÜBER SUMMEN, DIE SICH AUFHEBEN, ERWEIST SICH ALS FALSCH
Man nehme eine Uhr mit sechs Stunden und eine Liste von Zügen: „den Zeiger 1 Stunde vorwärts drehen“, „4 Stunden vorwärts“ und so weiter. Mit fünf Zügen von je einer Stunde bringt keine Gruppe davon den Zeiger je genau an den Anfang zurück. Mit sechs Zügen, welche auch immer, gelingt das stets irgendeiner Gruppe. Mathematiker schreiben diese Uhrenarithmetik als C₆, und die Zahl sechs ist hier die Davenport-Konstante der Uhr.
Nun stelle man r solche Uhren nebeneinander, und jeder Zug drehe jeden Zeiger um einen eigenen Betrag. Die Davenport-Konstante dieses Satzes von Uhren, geschrieben D(C₆^r), ist die kleinste Anzahl von Zügen, die eine Gruppe garantiert, deren Gesamtsumme jeden Zeiger zugleich an den Anfang zurückbringt — in den Worten der Arbeit eine Nullsummen-Teilfolge. Die Konstante hängt mit Problemen der Graphentheorie, der endlichen Geometrie, der Kombinatorik und der Faktorisierungstheorie zusammen.
Eine Formel von 1969
Es gibt eine einfache untere Schranke. Auf jeder Uhr nehme man fünf Ein-Stunden-Züge, die nur diese Uhr betreffen: Bei r Uhren ergibt das 5r Züge, unter denen sich keine Gruppe aufhebt. Es sind also mindestens 5r + 1 Züge nötig. Allgemein, für Uhren mit n Stunden, mindestens r(n − 1) + 1.
1969 vermuteten van Emde Boas und Kruyswijk, dass diese einfache Schranke immer die exakte Antwort ist:
D(C_n^r) = r(n − 1) + 1.
Für einige Fälle wurde sie in den 1960er-Jahren bewiesen, etwa für Uhren, deren Stundenzahl eine Potenz einer Primzahl ist, oder für höchstens zwei Uhren. Darüber hinaus blieb der exakte Wert unerreichbar: Noch 2018 war selbst der Fall von vier Sechs-Stunden-Uhren ungeklärt. Dennoch wurde die Vermutung zu „einem prominenten, seit Langem offenen Problem“ des Fachgebiets, und man erwartete, dass sie gilt.
116 Züge, die sich nie aufheben
Weidong Gao (Tianjin University), Alfred Geroldinger (Universität Graz), Guoqing Wang (Tiangong University) und Xiangneng Zeng (Sun Yat-Sen University) zeigen nun, dass sie nicht gilt.
Das Team setzt die Züge wie Bausteine zusammen:
- eine Liste von 24 Zügen auf fünf Sechs-Stunden-Uhren, aufgebaut aus einer kleinen Tabelle: Jede Gruppe davon, deren Gesamtsumme in eine kleine Menge von drei Positionen fällt, landet stets auf derselben, von null verschiedenen Position;
- zwei solche Listen, die diese drei Positionen teilen, was 48 Züge ergibt, ohne eine Gruppe, die sich aufhebt;
- eine separate Liste von 20 Zügen, in der sich ebenfalls keine Gruppe aufhebt.
Nebeneinandergestellt ergeben sie 2 × 48 + 20 = 116 Züge auf 23 Sechs-Stunden-Uhren, und keine Gruppe davon bringt jeden Zeiger an den Anfang zurück. Laut der Vermutung war 23 × 5 = 115 die längste mögliche Liste dieser Art. Für 23 Uhren ist die Davenport-Konstante also mindestens 117, nicht 116.
Kopien dieses Blocks lassen sich stapeln: Das allgemeine Ergebnis lautet D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, wobei ⌊r/23⌋ zählt, wie viele ganze Blöcke aus 23 in r passen. Die Vermutung ist daher für Sechs-Stunden-Uhren falsch, sobald r 23 erreicht, und für jedes größere r. Das Team merkt an, dass derselbe Satz auch ein vermutetes Ergebnis über Überdeckungen widerlegt.
Was offen bleibt
Der Beweis liefert nicht den wahren Wert von D(C₆^r), nur eine Schranke, die die Vermutung verbietet. Er sagt nichts Neues über weniger als 23 Uhren, wo die neue Schranke der alten Formel entspricht, und auch nichts über Uhren mit einer anderen Stundenzahl als sechs. Die Notiz umfasst fünf Seiten, und die Begutachtung durch Fachleute steht noch aus.
