Zum Inhalt
Alle Apps

Steinitz-Spaziergang — kurze Teilsummen in jeder Länge (3D)

Über diese App

Viele kurze Pfeile, jeder darf umgedreht werden: Bleibt der Spaziergang der Teilsummen in einer Kugel vom Radius √d, egal wie lang er ist? Zufällige Vorzeichen laufen wie √n davon, die gierige Wahl scheitert an einer Gegner-Folge, eine Suche über die ganze Folge bleibt drin. Regler für Schritte (bis 2000) und Dimension (2–12), Diagramme über n und über d. Euklidischer Steinitz–Bergström-Satz, openai/math Familie 097 (Lean-formalisiert). Exponatfähig.

Worum es geht

Man hat viele Pfeile der Länge höchstens 1 in fester Reihenfolge und darf jeden umdrehen. Lassen sich die Vorzeichen so wählen, dass der Spaziergang aus den aufaddierten Pfeilen nie weit vom Start wegläuft, egal wie lang er ist? Die Frage geht auf Ernst Steinitz (1913) zurück. Bekannt waren Schranken proportional zu d (Grinberg und Sevast’yanov 1980) und √(d·log n) (Banaszczyk 2012); vermutet war √d. Ein KI-erzeugtes Preprint aus github.com/openai/math (Familie 097) zeigt nach eigener Darstellung eine Schranke C·√d für jede Dimension und jede Folge. Laut Katalog ist der Hauptsatz in Lean formalisiert, begutachtet ist das Preprint nicht.

Was die App zeigt

Eine Kugel mit Radius √d umschließt den Startpunkt, und drei Spaziergänge laufen durch dieselbe Pfeilfolge. Zufällige Vorzeichen laufen wie √n davon. Die gierige Wahl sieht nur die Vergangenheit und scheitert an einer Gegner-Folge, deren Pfeile senkrecht auf der bisherigen Summe stehen. Eine ausbalancierte Wahl sucht über die ganze Folge und bleibt drin. Regler stellen bis 2000 Schritte und Dimension 2 bis 12 ein; Diagramme zeigen die Abstände über n und über d. Für d > 3 siehst du eine Projektion, die Farbe zählt die echte Länge.

Worauf achten

Verlängere den Spaziergang: Der zufällige läuft immer weiter hinaus, der ausbalancierte bleibt in der Kugel, unabhängig von der Zahl der Schritte. Erhöhe die Dimension und beobachte, dass die nötige Schranke mit √d wächst. Weniger geht nicht: Bei den Basisvektoren hat die Teilsumme nach d Schritten immer Länge √d. Der Beweis ist existenziell; er liefert keinen Algorithmus und keinen Zahlenwert für C, die Suche in der App ist eine Heuristik. Die App ist exponatfähig.

Häufige Fragen

Was besagt das Steinitz-Lemma?
Das Steinitz-Lemma sagt: Summieren sich endlich viele Vektoren der Länge höchstens 1 im d-dimensionalen Raum zu null, kann man sie so umordnen, dass jede Teilsumme durch eine Konstante beschränkt ist, die nur von d abhängt. Die Zahl der Vektoren spielt keine Rolle. Offen war, wie diese Konstante von d abhängt.
Was bedeutet Diskrepanz bei Vorzeichenwahl?
Bei der Vorzeichenwahl versieht man jeden Vektor einer Folge mit + oder − und betrachtet die Länge der Teilsummen. Die Diskrepanz ist die kleinste erreichbare größte Teilsumme. Zufällige Vorzeichen ergeben typischerweise Teilsummen der Größe √n, geschickte Wahl kann sie unabhängig von n halten.
Ist die √d-Schranke für Teilsummen bewiesen?
Ein KI-erzeugtes Preprint aus dem Katalog github.com/openai/math (Familie 097) beweist nach eigener Darstellung, dass es eine feste Konstante C gibt, mit der für jede Dimension und jede Folge alle Teilsummen höchstens C·√d lang bleiben; daraus folgt auch die Steinitz-Version. Laut Katalog ist der Hauptsatz in Lean formalisiert. Das Preprint ist noch nicht begutachtet.
Was kann ich in dieser App ausprobieren?
Du stellst Schrittzahl und Dimension ein und vergleichst drei Vorzeichenstrategien: Zufall, gierige Wahl und eine Suche über die ganze Folge. Die Kugel vom Radius √d zeigt, wer drinbleibt. Diagramme tragen die Abstände über n und über d auf.

Fach: Offene Probleme, gelöst von KI

Mehr aus Offene Probleme, gelöst von KI

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps