Lineale und Lineal-Vermutung

02/04/2009 - 23:22 von Rainer Rosenthal | Report spam
Liebe dsm-Gemeinde,

der Lineal-Virus hat seit wenigen Wochen einige Leute erneut
angesteckt, nachdem er nun für viele Monate geschlummert hatte.
In einem Forum bzw. in Mails mit CC haben Hugo Pförtner, Peter
Luschny, Klaus Nagel und ich versucht, uns wieder in das Thema
hinein zu denken. Ich möchte aber das Forum dsm nutzen, um an die
Lineale zu erinnern, die hier einst fleissig diskutiert worden
waren; siehe Schlussbemerkung unten.


1. Lineale und die Lineal-Vermutung
=
Wir möchten gerne für jede Lànge L alle Lineale bestimmen, die jede
Distanz von 0 bis L zu messen gestatten (vollstàndige Lineale). Inbesondere
interessieren die mit besonders wenigen Marken, denn alle anderen entstehen
aus solchen Linealen durch beliebiges Hinzufügen weiterer Marken.

Wir bezeichnen jede Menge H natürlicher Zahlen mit 0 als kleinster
und L als grösster Zahl als "Lineal der Lànge L". Die Elemente von H
sind die "Marken" des Lineals.
Die Distanzen, die man damit messen kann, sind alle Zahlen |x-y|,
wobei x und y Marken sind.

Beispiele: H1 = {0,1,6,8} ist das Lineal 0-1-.-.-.-.-6-.-8
Die Menge der Distanzen, die man damit messen kann, ist
Dist(H1) = {0,1,2,5,6,7,8}

Dieses Lineal ist nicht vollstàndig, weil man die
Distanzen 3 und 4 nicht messen kann.

Um ein vollstàndiges Lineal aus H1 zu erhalten, kann man
beispielsweise die Marke 3 hinzufügen.
H2 = {0,1,3,6,8} ist aber auch noch nicht vollstàndig, weil
in Dist(H2) = {0,1,2,3,5,6,7,8} noch Distanz 4 fehlt.

Fügen wir zu H2 die Marke 4 hinzu, dann ist auch Distanz 4
messbar. Auch andere Marken sind denkbar, um die letzte
fehlende Distanz 4 zu messen; z.B. Marke 5. Nehmen wir als
drittes Beispiel also H3 = {0,1,3,5,6,8}. Dies Lineal ist
vollstàndig, denn nun ist jede Distanz von 0 bis 8 messbar.

Das Lineal H3 làsst sich aber noch reduzieren, ohne die
Vollstàndigkeit einzubüssen:
H4 = {0,1,5,6,8}. Es ist leicht zu sehen, dass weitere
Reduzierung nicht mehr möglich ist, ohne die Vollstàndigkeit
zu verlieren.

Auf der Suche nach schnellen Algorithmen zur Bestimmung aller reduzierten
vollstàndigen Lineale wurde die L-Methode gefunden, die schrittweise
Lineale konstruiert unter Berücksichtigung der jeweils grössten noch zu
realisierenden Distanz.

Die praktische Umsetzung der L-Methode hat viele Lineale gefunden, und
alle Lineal-Freunde in dsm vermuten stark, dass die L-Methode alle
reduzierten vollstàndigen Lineale zu finden gestattet. Diese grosse
"Lineal-Vermutung" ist aber bislang unbewiesen geblieben.


2. Verallgemeinerung der Lineal-Vermutung
=
Zwar wurde die Lineal-Vermutung für vollstàndige Lineale formuliert, weil
sie bei der Suche nach reduzierten vollstàndigen Linealen zur Rechtfertigung
der L-Methode benötigt wird, aber vielleicht genügt schon die Reduziertheit
eines Lineals, damit es durch die L-Methode konstruiert werden kann!

Verallgemeinerte Lineal-Vermutung

Ein Lineal H heisst reduziert, wenn seine
Distanzenmenge Dist(H) grösser ist als die
Distanzenmenge jeder echten Untermenge von H.
Jedes reduzierte Lineal làsst sich mit der
L-Methode aus seiner Distanzenmenge konstruieren.

Als Beispiel wàhlen wir das obige Lineal H = H1 = {0,1,6,8}, das zwar nicht
vollstàndig ist, weil in seiner Distanzenmenge Dist(H) = {0,1,2,5,6,7,8}
die Elemente 3 und 4 fehlen, aber H ist reduziert:
Ohne die Marke 1 bekommt man nur die Distanzen 0,2,6,8.
Ohne die Marke 6 bekommt man nur die Distanzen 0,1,7,8.

Die Konstruktion von H gelingt mit der L-Methode wie folgt.
Es werden schrittweise, beginnend mit K_0 = {0,8} weitere
Marken hinzugefügt, solange bis die von K_0, K_1, ... gemessenen
Distanzen gleich denen des Lineals H sind. Nach jedem Schritt i
wird die Menge U_i der Distanzen bestimmt, die durch K_i noch
nicht gemessen werden, die aber zu Dist(H) gehören. Sobald ein
U_i leer ist, sind alle Distanzen gefunden.
ACHTUNG: anders als bei vollstàndigen Linealen muss stets
geprüft werden, ob Dist(K_i) Elemente enthàlt, die
nicht zu Dist(H) gehören. Das ist ja bei einem voll-
stàndigen Lineal H nicht möglich.

Schritt 0: Setze K_0 = {0,8} und U_0 = Dist(H1) minus Dist(K_0)
Damit enthàlt U_0 die vom Lineal K_0 noch nicht
messbaren Distanzen 1,2,5,6,7.

Schritt 1: Wàhle eine Marke, die grösste nicht-messbare Distanz,
also die 7, zu messen gestattet.
Wir wàhlen Marke e_1 = 1 und erhalten K_1 = {0,1,8}.
Es ist Dist(K_1) = {0,1,7,8}, also U_1 = {2,5,6}.

Schritt 2: Wàhle eine Marke, die grösste nicht-messbare Distanz,
also die 6, zu messen gestattet.
Wir wàhlen Marke e_2 = 6 und erhalten K_2 = {0,1,6,8}.
Es ist Dist(K_2) = {0,1,2,5,6,7,8}, also U_2 = {}.

Weil U_2 leer ist, ist die Konstruktion erfolgreich beendet worden.


3. Weitere Verallgemeinerung misslingt
=
Um ein Beispiel für das Misslingen der L-Methode zu finden, kann man
die Voraussetzungen noch weiter modifizieren und beispielsweise
fordern, ein reduziertes Lineal zu konstruieren, von dem nur einige
Distanzen bekannt sind.
So kann z.B. das Lineal H = {0,2,7,8} die Distanzen {0,1,5,8} messen,
aus dieser Teilmenge aller seiner Distanzen kann es aber nicht
mit der L-Methode konstruiert werden. Das sieht man sofort, wenn man
Schritt 1 durchführen will, weil man dann eine Marke e_1 finden
muss, die die grösste fehlende Distanz, also die 5, messbar macht.
Dafür kommen aber nur die Marken 3 oder 5 in Frage, die in H nicht
vorkommen.
Das Scheitern ist illustrativ für die Befürchtungen, die bzgl. der
Lineal-Vermutung bestehen: dass sich eine làngste fehlende Distanz
'irgendwo in der Mitte' befindet, also nur durch *zwei* neue Marken
bestimmt werden kann, wàhrend die L-Methode ja immer nur eine weitere
Marke sucht.

4. Schlussbemerkung

Ich würde mich freuen, wenn Aussenstehende für das Lineal-Thema
interessiert worden sind. Ich möchte unbedingt auf die umfassende
Darstellung bei Peter Luschny hinweisen:
www.luschny.de/math/rulers/prulers.html

Gruss,
Rainer Rosenthal
r.rosenthaleb.de
 

Lesen sie die antworten

#1 Rainer Rosenthal
03/04/2009 - 10:14 | Warnen spam
Rainer Rosenthal schrieb:

r.rosenthaleb.de


^^ hier fehlt @w

Ein aufmerksamer Leser hat mich auf diesen Schreibfehler
hingewiesen in einer kurzen Mail. Ein anderer hat mich
auf das Stichwort 'Golombizitàt' aufmerksam gemacht und
googelnd bin ich auf einen ausfürhrlichen Thread von
vor 6 Jahren(!) gestossen: http://tinyurl.com/Lineal2003
Eine Fundgrube für Linealisten.

Sehr hübsch zu lesen ist die Passage, in der Klaus Nagel warnt,
er könne einen von Peter Luschny ausgesetzten Preis gewinnen:
==um Dich das Fürchten zu lehren:

L = 113 M = 19
1. : 0 1 2 3 4 11 44 60 65 75 81 87 93 99 105 110 111 112 113
1 1 1 1 7 33 16 5 10 6 6 6 6 6 5 1 1 1

110 844691 rekursive Aufrufe 351.334 Sekunden

Und es sind noch 13 Tage hin und ich kenne eine große Firma mit
Hunderten von PCs und ich weiß, wie man dieses Problem aufteilt!
==
Also noch eimal für Interessenten: http://tinyurl.com/Lineal2003
Ach ja: und die Rechner sind in den letzten 6 Jahren eher noch
schneller geworden ;-)

Gruss,
Rainer Rosenthal

Ähnliche fragen