31.12.2008 · Zum Ende des Jahres der Mathematik: Beim Golomb-Lineal geht es um das Messen mit möglichst wenigen Markierungen - und die Suche nach Lösungen lässt Köpfe und Computer rauchen.
Von Heinrich Hemme
©
Kunst des sparsamen Messens: ein Golomb-Lineal vierter Ordnung
Ein einfaches, dreißig Zentimeter langes Lineal hat, mit null Zentimeter beginnend und mit dreißig Zentimeter endend, insgesamt einunddreißig Markierungsstriche im Abstand von je einem Zentimeter. Man kann mit diesem Lineal durch einmaliges Anlegen jede ganzzahlige Länge von einem bis zu dreißig Zentimeter abmessen. In den Sechzigerjahren des vergangenen Jahrhunderts fragte sich der amerikanische Mathematiker Solomon W. Golomb von der University of Southern California, ob auf dem Lineal wirklich alle einunddreißig Markierungen notwendig sind, um diese dreißig Längen zu messen. In der Tat kommt man mit deutlich weniger Markierungen aus, wenn man nicht jede Messung mit der Nullmarkierung des Lineals beginnt. Auf dieser Grundlage beruhen die sogenannten Golomb-Lineale, die übrigens nicht nur eine mathematische Kuriosität sind. Sie spielen beispielsweise bei der Verteilung von Rundfunkbändern und beim Aufstellen von Antennengruppen in der Radioastronomie oder in der Geodäsie eine wichtige Rolle.
Um eine Länge von sagen wir einmal drei Zentimetern zu messen, legt man normalerweise die Null-Markierung des Lineals an das linke Ende der zu messenden Strecke. Die Markierung „3“ fällt dann auf das rechte. Man kann stattdessen aber auch die Markierungen „4“ und „7“ anlegen oder, von rechts ausgehend, die Markierungen „6“ und „3“. Jede Messung stützt sich also auf ein Paar von Markierungen. Hat ein Lineal insgesamt 11 Markierungen – von 0 bis 10 –, so kann man jede davon mit den jeweils 10 anderen zu einem Paar kombinieren, wobei die Richtung keine Rolle spielt. Allgemein bedeutet das, dass das Lineal mit n Markierungen n(n-1) Markierungspaare hat. Da es aber kein Unterschied ist, ob man von links nach rechts („3“ auf „6“) oder von rechts nach links („6“ auf „3“) misst, jedes Paar also zwei Mal identisch vorkommt, hat man mit den n(n-1) Markierungspaaren nur n(n-1)/2 Messmöglichkeiten.
Auf der Suche nach dem einfachsten perfekten Lineal
Bei einem gewöhnlichen Lineal ergeben viele dieser Messmöglichkeiten – etwa von „2“ auf „5“ oder von „3“ auf „6“ – gleiche Längen. Solomon W. Golomb ist es jedoch gelungen, Lineale zu konstruieren, deren Markierungen – die im Übrigen nicht mehr gleiche Abstände voneinander aufweisen – so verteilt sind, dass alle Messmöglichkeiten zu verschiedenen Längen führen. Solche Lineale nennt man seither Golomb-Lineale. Ein Golomb-Lineal mit n Markierungen, mit dem man alle ganzzahligen Längen von einem Zentimeter bis zu n(n-1)/2 Zentimeter messen kann, wird als perfekt bezeichnet.
Das einfachste perfekte Golomb-Lineal ist einen Zentimeter lang und hat nur an beiden Enden je eine Markierung. Es wird in mathematischer Notation als (0, 1) dargestellt, und man kann mit ihm nur eine Länge von einem Zentimeter messen. Das nächste perfekte Golomb-Lineal ist (0, 1, 3). Es ist drei Zentimeter lang und hat Markierungen bei null, bei einem und bei drei Zentimeter. Zwischen den Markierungen 0 und 1 hat das Lineal eine Länge von einem Zentimeter, zwischen 1 und 3 von zwei Zentimetern und zwischen 0 und 3 von drei Zentimetern. Mit dem vierten perfekten Golomb-Lineal (0, 1, 4, 6), das sechs Zentimeter lang ist, lassen sich alle ganzzahligen Längen von einem bis zu sechs Zentimetern messen.
Ausweichen auf die zweitbeste Variante
Wie bei so vielem auf der Welt ist Perfektion auch bei Golomb-Linealen eine eher seltene Eigenschaft. Solomon W. Golomb bewies schon vor vierzig Jahren, dass es perfekte Golomb-Lineale nur mit zwei, drei und vier Markierungen geben kann. Für alle Lineale mit mehr als vier Markierungen kommen manche Längen entweder mehrfach oder gar nicht vor.
Wenn man das Beste nicht haben kann, begnügt man sich mit dem Zweitbesten. Das sehen auch Mathematiker so. Darum ersetzen sie die Forderung, dass bei einem Golomb-Lineal mit n Markierungen alle Längen von 1 bis n(n-1)/2 vorkommen müssen, durch die etwas genügsamere, dass Abstände zwischen allen Markierungspaaren verschieden sein müssen und dass das Lineal so kurz wie möglich sein soll. Ein solch kürzestmögliches Golomb-Lineal mit n Markierungen wird als optimales Golomb-Lineal n-ter Ordnung bezeichnet. Die drei perfekten Golomb-Lineale sind gleichzeitig auch die optimalen Lineale 2., 3. und 4. Ordnung.
Optimale Golomb-Lineale zu finden ist eine schwierige Angelegenheit, denn unglücklicherweise steigt der Aufwand der Suche exponentiell mit ihrer Ordnung an. Die optimalen Golomb-Lineale 5., 6. und 7. Ordnung wurden bereits 1952 von Wallace C. Babcock von der Firma Bell mit Bleistift und Papier gefunden, wovon Golomb allerdings bei der Veröffentlichung seiner Lineale nichts gewusst hat.
Optimale Golomb-Linale 5. Ordnung haben die Länge L(5) = 11, und es gibt, von den spiegelbildlichen Markierungsanordnungen einmal abgesehen, die beiden Formen (0, 1, 4, 9, 11) und (0, 2, 7, 8, 11). Die optimalen Golomb-Lineale 6. und 7. Ordnung sind L(6) = 17 und L(7) = 25 lang. Die Längen der nächsten vier optimalen Golomb-Lineale fand William Mixon im Jahr 1972 mit einem Computer. Sie betragen L(8) = 34, L(9) = 44, L(10) = 55 und L(11) = 72. 1979 und 1980 konnte John P. Robinson von der University of Iowa beweisen, dass L(12) = 85 und L(13) = 106 sind. James B. Shearer von der Firma IBM bestimmte 1985 und 1986 die Längen L(14) = 127, L(15) = 151 und L(16) = 177, und W. Olin Sibert fand 1993 L(17) = 199 und L(18) = 216.
Computer im Netzwerk
Nun wurde der Aufwand so groß, dass ein einzelner Computer ihn nicht mehr bewältigen konnte. 1995 ließen deshalb Apostolos Dollas, William T. Rankin und David McCracken von der Duke University in North Carolina zwölf Computer gleichzeitig nach dem optimalen Golomb-Lineal 19. Ordnung suchen. Nach monatelangen Berechnungen konnten sie schließlich beweisen, dass L(19) = 246 ist. 1997 starteten Mark Garry und David Vanderschel im Internet ein Projekt, bei dem viele Computer sich gemeinsam auf die Suche nach den nächsten optimalen Golomb-Linealen machten. Das Projekt war erfolgreich, und bis 1999 wurden L(20) = 283, L(21) = 333, L(22) = 356 und L(23) =372 entdeckt.
Im Jahr 1997 gründete David C. McNett die Gesellschaft Distributed Computing Technologies mit dem Ziel, riesige Rechenprojekte über das Internet auf viele tausend private Computer zu verteilen. Drei Jahre später startete diese Gesellschaft das Projekt OGR-24, mit dem das optimale Golomb-Lineal 24. Ordnung gefunden werden sollte. Fast 42 000 Menschen beteiligten sich mit ihren Computern an dieser Suche. Nach mehr als vier Jahren fand man es schließlich. Es hat eine Länge L(24) = 425. Kurz nach dem Beginn von OGR-24 wurde auch OGR-25 für die Suche nach dem optimalen Golomb-Lineal 25. Ordnung gestartet. Diesmal dauerte die Suche, an der etwa 125 000 Menschen auf der ganzen Welt beteiligt waren, acht Jahre. Vor kurzem ist es dann so weit gewesen: Der Beweis wurde erbracht, dass es nur ein einziges optimales Golomb-Lineal 25. Ordnung gibt. Es hat die Form (0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207, 214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480) und die Länge 480. Und wie sieht das Golomb-Lineal 26. Ordnung aus? Vermutlich werden wir noch viele Jahre auf die Antwort warten müssen.
