Borsuk-Vermutung

Borsuk-Vermutung
Johannes Lindl, 27. Juni 2015
Karol Borsuk’s Aufsatz ”Drei Sätze über die n-dimensionale euklidische Sphäre”
aus dem Jahr 1933 ist berühmt, weil er ein wichtiges von Stanislaw Ulam vermutetes Resultat enthält, das man jetzt als den Borsuk-Ulam-Satz kennt:
Jede stetige Abbildung f : S d → Rd bildet zwei gegenüberliegende Punkte der
Sphäre S d auf denselben Punkt im Rd ab.
Am Ende dieses Aufsatzes wird aber auch noch ein berühmtes Problem gestellt,
dass als Borsuk-Vermutung bekannt geworden ist:
Kann jede Menge S ⊆ Rd von beschränktem, positivem Durchmesser
in höchstens d + 1 Mengen von kleinerem Durchmesser zerlegt werden?
Die Schranke d + 1 ist dabei bestmöglich: Wenn S ein reguläres d-dimensionales
Simplex (d+1 Ecken; Dreieck ist 2-dim Simplex, Tetraeder ist 3-dim Simplex...)
ist, oder aber auch nur die Menge seiner d + 1 Ecken, dann kann kein Teil
einer Zerlegung in Teile von kleinerem Durchmesser mehr als eine der Ecken
enthalten.Wenn f(d) die kleinste Zahl bezeichnet, so dass jede beschränkte Menge
S ⊆ Rd eine Durchmesser-reduzierende Zerlegung in f(d) Teile hat, dann zeigt also
das Beispiel des regulären Simplex, dass f(d) ≥ d + 1 ist. Die Borsuk-Vermutung
wurde für den Fall bewiesen, wenn S eine Sphäre ist (von Borsuk selbst), für
glatte Körper S, und auch für d ≤ 3... aber die allgemeine Vermutung blieb
offen. Die beste allgemeine obere Schranke für f(d) ist (1,23)d für alle großen d
(von Oded Schramm).
Aber 1993 konnten Jeff Kahn und Gill Kalai zeigen, dass
√
d
f(d) ≥ (1, 2) für alle großen d gilt, was die Vermutung deutlich widerlegt.
Folgendes Gegenbeispiel für d = 561 ist eine Abwandlung, die von Andrei M.
Raigorodskii und Bernulf Weißbach stammt. Heute wissen wir, dass die BorsukVermutung schon ab Dimension 64 falsch ist (Wikipedia).
Satz. Sei q = pm eine Primzahlpotenz, sei n := 4q - 2, und sei
d := n2 = (2q - 1)(4q - 3). Dann gibt es eine Menge S ⊆ {+1, −1}d von 2n−2
Punkten im Rd , so dass jede Zerlegung von S in Teile von kleinerem Durchmesser
mindestens
2n−2
Pq−2 n−1
i=0
(
i
)
Teile benötigt. Für q = 9 impliziert dies, dass die Borsuk-Vermutung
in Dimen√
sion d = 561 falsch ist. Weiterhin folgt daraus f(d) > (1, 2) d für alle sehr großen
d.
1
Beweisskizze. Die Konstruktion der Menge S geschieht in vier Schritten.
(1) Sei q eine Primzahlpotenz, n := 4q - 2, und sei
Q := { x ∈ {+1,-1}n : x1 = 1, #{ i : xi = -1} ist gerade}.
Dieses Q ist eine Menge von 2n−2 Vektoren im Rn .Wir werden sehen, dass
hx,yi ≡ 2 (mod 4) für alle Vektoren x, y ∈ Q gilt. Wir nennen x, y fast orthogonal,
wenn |hx,yi| = 2 ist.Wir werden zeigen, dass eine Teilmenge Q’ ⊆ Q, diePkeine fast
n−1
orthogonalen Vektoren enthält, ”klein” sein muss: für sie gilt |Q’| ≤ q−2
i=0
i
(2) Aus Q konstruieren wir die Menge R := { xxT : x ∈ Q} von 2n−2 symmetrischen (n×n)-Matrizen vom Rang 1.Wir interpretieren sie als Vektoren mit
2
n2 Komponenten, R ⊆ Rn . Wir werden zeigen, dass es nur spitze Winkel zwischen diesen Vektoren gibt: sie haben positives Skalarprodukt, das mindestens
4 ist. Und wenn eine Teilmenge R’ ⊆ R keine zwei P
Vektoren mit minimalem
n−1
Skalarprodukt 4 enthält, dann ist |R’| ”klein”: |R’| ≤ q−2
i=0
i
n
(3) Aus R erhalten wir eine Menge von Vektoren im R( 2 ) , deren Koordinaten
durch die Einträge unter der Diagonalen der entsprechenden Matrizen gegeben
sind: S := { (xxT )i>j : xxT ∈ R}. Die Menge S besteht aus 2n−2 Punkten. Den
maximalen Abstand zwischen diesen Punkten erhält man genau dann, wenn die
entsprechenden Vektoren x, y ∈ Q fast-orthogonal sind. Wir schließen daraus,
dass jede
Teilmenge
S’ ⊆ S von kleinerem Durchmesser als S ”klein” sein muss:
Pq−2
n−1
|S’| ≤ i=0 i
(4) Abschätzungen: Aus (3) sehen wir, dass jede Durchmesser-reduzierende Zer24q−4
Teile hat. Deshalb gilt
legung von S mindestens g(q) := Pq−2
4q−3
i=0 ( i )
f(d) ≥ max{g(q), d + 1} für d = n2 = (2q - 1)(4q - 3). Also haben wir ein
Gegenbeispiel für die Borsuk-Vermutung in Dimension d = (2q - 1)(4q - 3) gefunden, wenn g(q) > (2q - 1)(4q - 3) + 1 ist. Wir werden nachrechnen, dass
g(9) > 562 ist, und damit ein Gegenbeispiel in Dimension d = 561 erhalten,
und
√
27 q
e
d
weiterhin g(q) > 64q2 ( 16 ) was die asymptotische Schranke f(d) > (1,2) für alle
großen d liefert.
Die Borsuk-Vermutung ist für d≤3 bewiesenermaßen richtig, aber sie konnte
bisher für keine größere Dimension gezeigt werden. Im Gegensatz dazu ist sie
wahr bis d = 8, wenn wir sie auf Teilmengen der Form S ⊆ {1,-1}d einschränken,
wie in der obigen Konstruktion. Aber es ist sehr wahrscheinlich, dass es auch in
”vernünftig kleinen” Dimensionen schon Gegenbeispiele zur Borsuk-Vermutung
gibt.
Quelle: Martin Aigner, Günther M. Ziegler: ”Das Buch der Beweise”
2

Download Report