DER GRÖSSTE BETRAG, DEN MAN NICHT ZAHLEN KANN, JETZT SCHARF BEGRENZT

Man stelle sich eine Kasse vor, die nur wenige Münzsorten annimmt, in unbegrenzter Menge, und nie Wechselgeld herausgibt. Manche Beträge lassen sich exakt bezahlen, andere nie. Mathematiker nennen die Münzwerte Erzeuger (generators) und stellen eine trügerisch einfache Frage: Was ist der größte Betrag, der sich nicht bezahlen lässt?

Beträge, die sich nie bezahlen lassen

Man nehme ganze Zahlen a₁ < a₂ < … < aₙ, die keinen gemeinsamen Teiler aller Zahlen haben. Eine Summe, die man durch Addieren dieser Zahlen erhält, jede beliebig oft, heißt „darstellbar“. Nur endlich viele ganze Zahlen sind es nicht; die größte davon ist die Frobenius-Zahl F. (Ist einer der Werte 1, lässt sich alles bezahlen, und man setzt F = −1.)

Ein kleines Beispiel: Mit Münzen zu 3, 4 und 6 kann man 3, 4, 6, 7, 8 und jeden Betrag danach bezahlen, aber nie 1, 2 oder 5. Also ist F = 5. Man beachte, dass 3 und 6 einen gemeinsamen Teiler haben; entscheidend ist, dass kein Teiler allen dreien gemeinsam ist.

Für zwei Münzen gibt es eine exakte Antwort, die Formel von Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Für drei oder mehr besteht die Arbeit darin, F abzuschätzen: zu beweisen, dass F einen aus den Münzen berechneten Wert nicht überschreiten kann.

Ein hartnäckiger Faktor 2

Paul Erdős und Ronald Graham bewiesen für drei oder mehr Erzeuger:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Dabei ist aₙ der größte Wert, aₙ₋₁ der zweitgrößte, n die Anzahl der Werte, und ⌊ ⌋ bedeutet Abrunden. Wie die Formel von Sylvester enthält sie die beiden größten Münzen.

Sie schätzten außerdem den ungünstigsten Fall ab, also das größtmögliche F, wenn alle n Werte höchstens t betragen. Die Lücke zwischen ihren Abschätzungen, etwa ein Faktor 2, führte zu einer Vermutung, die als Erdős-Problem Nr. 433 verzeichnet ist. Jacques Dixmier löste sie und bewies zudem eine einfachere Schranke, die für jede Menge gilt: F ≤ aₙ²/(n − 1). Der Faktor 2 ist verschwunden, aber auch die zweitgrößte Münze.

Beide größten Münzen behalten

Lin Chen, Tingwei Hu, Yuchen Mao und Guochuan Zhang vom College of Computer Science and Technology der Zhejiang-Universität wollten beides: keinen Faktor 2 und trotzdem die zweitgrößte Münze in der Formel. Ihre Antwort, gültig für jede Menge aus zwei oder mehr Werten:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Dabei bedeutet ⌈ ⌉ Aufrunden. Verglichen mit Erdős und Graham ist der Faktor 2 verschwunden, um den Preis, dass durch n − 1 statt durch n geteilt und aufgerundet wird. Verglichen mit Dixmier kann die neue Schranke deutlich kleiner sein, wenn die zweitgrößte Münze klein gegenüber der größten ist.

Im Beispiel 3, 4, 6 liefert die Schranke von Erdős und Graham 10, die von Dixmier 18 und die neue 4 × 3 − 6 − 1 = 5, genau den wahren Wert. Das ist keine Überraschung: Diese Menge gehört zu der unten beschriebenen Familie von Extremfällen, die so gebaut ist, dass sie die Schranke exakt erreicht; einen Vergleich an typischen Mengen liefert die Arbeit nicht.

Beträge nach Rest sortieren

Der Beweis folgt dem Weg von Erdős und Graham. Man sortiere jeden Betrag nach seinem Rest bei Division durch die größte Münze aₙ. Sobald eine Summe der kleineren Münzen einen bestimmten Rest erreicht, erreicht man durch Hinzufügen von Kopien von aₙ jeden größeren Betrag mit demselben Rest. Die Aufgabe besteht darin zu zeigen, dass sich jeder Rest günstig erreichen lässt.

Das zentrale Werkzeug ist der Satz von Kneser darüber, wie groß eine Menge von Summen mindestens sein muss. Erdős und Graham zeigten damit, dass Summen aus etwa aₙ/n Münzen mehr als die Hälfte der Reste abdecken, und verdoppelten dann, um alle abzudecken. Jede Münze in diesen Summen ist höchstens aₙ₋₁ wert, also verdoppelt eine Verdopplung der Münzanzahl die Kosten: daher der Faktor 2.

Der neue Beweis verwendet Summen aus ⌈aₙ/(n − 1)⌉ Münzen. Wenn diese Summen einige Reste verfehlen, besagt der Satz von Kneser, dass die fehlenden nicht zufällig verstreut sind: Sie bilden ganze Familien von Resten in regelmäßigen Abständen. Je mehr Familien fehlen, desto mehr der kleineren Münzen müssen sich in jeder erreichten Familie drängen; also enthält jede dieser Familien einige kleine Münzen, und die wenigen zusätzlichen Münzen, die man zum Erreichen der fehlenden Familien braucht, sind billig. Die Gesamtkosten übersteigen nie ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Dieser erste Schritt liefert die Schranke ohne ihr abschließendes „− 1“. Die letzte Einheit stammt aus einem separaten Argument, das auf einem Satz von Scherk und Kemperman über Summen beruht, die sich nur auf eine einzige Weise bilden lassen: Es zeigt, dass der Grenzbetrag aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ selbst immer bezahlt werden kann. Laut der Danksagung bewiesen die Autoren zunächst die schwächere Schranke; GPT-6 half dann, das Argument zu finden, das sie um eins senkt, und unterstützte außerdem beim Beweis, dass die Schranke nicht gesenkt werden kann, sowie bei der Überarbeitung des Englischen. Die Autoren erklären, dass sie die Verantwortung für das endgültige Manuskript übernehmen.

Fälle, die die Grenze genau treffen

Diese Schranke kann nicht gesenkt werden: Für jedes n ≥ 3 konstruieren die Autoren unendlich viele Mengen, bei denen F genau gleich der Schranke ist. Man nehme ein beliebiges q ≥ 2 und die Werte q, 2q, …, (n − 1)q sowie (n − 2)q + 1. Alle bis auf einen sind Vielfache von q, sie bezahlen also nichts, was q allein nicht auch bezahlen könnte. Die Menge verhält sich wie zwei Münzen, q und (n − 2)q + 1, und die Formel von Sylvester ergibt ein F, das genau mit der neuen Schranke übereinstimmt. Mit n = 3 und q = 3 liefert dieses Rezept genau das obige Beispiel 3, 4, 6.

Weniger Münzen, eine niedrigere Decke

Die Schranke lässt sich auch als Aussage über Dichte lesen. Sie gilt für jede reduzierte Menge aus den i kleinsten Werten plus dem größten, solange diese noch keinen gemeinsamen Teiler haben. Münzen wegzunehmen kann das Bezahlen nur erschweren, also gilt eine für die reduzierte Menge bewiesene Obergrenze auch für die vollständige. Was das Ergebnis bestimmt, ist ungefähr aᵢ/i, der Kehrwert dessen, wie dicht die ersten i Werte die Zahlen von 1 bis aᵢ füllen: Die dichteste Gruppe gewinnt. Insbesondere, so merken die Autoren an, kann die zweitgrößte Münze einfach beiseitegelassen werden, wann immer die übrigen Münzen noch keinen gemeinsamen Teiler aller haben.

Die Arbeit bleibt rein theoretisch: Sie nennt keine Zahl dazu, wie viel kleiner die neue Schranke bei typischen Münzmengen ist, und ihre Schärfe ist nur für drei oder mehr Münzwerte bewiesen.