StartseiteMathlog

Theorema Magnum MMXVI: Erdős‘ Diskrepanz-Problem

Von / 3. Februar 2022 / 16 Kommentare / Seite 1 von 3 / Auf einer Seite lesen
Mehr

Pál Erdős war ein aus Ungarn stammender Mathematiker, der vor allem für zahlreiche Vermutungen bekannt ist, auf deren Lösung er Geldpreise aussetzte, 50 Dollar bei kleineren Vermutungen, vierstellige Beträge bei größeren. Eine bekannte Vermutung, die er bereits 1932 als 19-Jähriger und damals noch ohne Geldpreis – später lobte er dann 500 Dollar aus – aufgestellt hatte, war die Diskrepanz-Vermutung. Die wird anschaulich so erklärt:
Ein Mensch ist auf einem Felsvorsprung gefangen. Zwei Schritte zu seiner Linken befindet sich ein Abgrund, zwei Schritte zur Rechten eine Schlangengrube. Um ihn zu quälen, zwingt ein bösartiger Wärter sein Opfer, sich ständig nach links und rechts zu bewegen. Der Gefangene muss eine Folge von Schritten finden, mit der er den Gefahren auf beiden Seiten ausweicht. Bewegt er sich zuerst nach rechts, muss er sofort nach links zurück, sonst ist der Absturz vorprogrammiert.
Abwechselnd in beide Richtungen zu gehen, scheint die Lösung zu sein – doch hier ist der Haken: Der Gefangene muss seine Schrittfolge im Vorhinein festlegen, und der Wärter kann bestimmen, dass er aus der festgelegten Folge nur jeden zweiten Schritt ausführt, beginnend mit dem zweiten. Oder er lässt nur jeden dritten, vierten, … zu. Die Frage lautet: Existiert eine Taktik, mit welcher der Gefangene am Leben bleibt, unabhängig von der Strategie, die sein Peiniger wählt?
Die Diskrepanz-Vermutung besagte, dass eine solche Taktik nicht existiert – und zwar nicht nur für C=1, sondern auch für jede andere Entfernung zum Abgrund.
Die mathematische Formulierung ist wie folgt: Für jede Folge xn, deren Glieder alle 1 oder -1 sind, und für jede ganze Zahl C gibt es ganze Zahlen k und d mit \vert\sum_{i=1}^k x_{di}\vert>C.
Später wurde die Vermutung allgemeiner für Hilbert-Räume statt für R formuliert. Man hat also eine Folge in einem Hilbert-Raum, deren Glieder Norm 1 haben und dann soll es zu jeder ganzen Zahl C wieder k und d geben mit \Vert \sum_{i=1}^k x_{di}\Vert >C.

Nach Meinung von Erdős sollten Theorien nicht alles in der Mathematik ausmachen. Es gebe genug Probleme, die man mit fortgeschrittenen Methoden nicht angehen könne und die trotzdem nicht uninteressant seien. Trotzdem hat sich eine Diskrepanztheorie entwickelt, bei der es grob gesagt um die Approximierbarkeit kontinuierlicher Objekte durch diskrete geht. Beispielsweise bewies Erdős’ früherer Student Joel Spencer 1985, dass man zu je n Teilmengen S_1,\ldots,S_n\subset\left\{1,...,n\right\} eine Zerlegung von {1,…,n} in zwei Teilmengen R und B finden kann, die bezüglich jedem der Si annähernd ausgeglichen ist: \vert \sharp(S_i\cap R)-\frac{1}{2}\sharp S_i\vert\le 3\sqrt{n}. Solche Resultate hatten Anwendungen auf Approximationsalgorithmen und numerische Verfahren. Eine spekatakuläre Anwendung der Diskrepanztheorie wurde das seit 1959 offene Kadison-Singer-Problem aus der Theorie der Operatoralgebren über die Eindeutigkeit der durch den Satz von Hahn-Banach gegebenen Erweiterung gewisser linearer Funktionale auf C*-Algebren: auf einer maximalen abelschen Unteralgebra {\mathcal A}\subset{\mathcal B}(l^2 {\bf N}) hat man einen reinen Zustand ρ (ein positives Funktional, das keine Konvexkombination positiver Funktionale ist) und fragt nach der Eindeutigkeit der Fortsetzung auf {\mathcal B}(l^2{\bf N}). (Physikalisch ist das analog den in der Quantenmechanik den Observablen entsprechenden Wahrscheinlichkeitsverteilungen als lineare Funktionale auf kommutierenden Operatoren, die man dann auf andere Observablen ausdehnen will, welche nichtkommutierenden Operatoren entsprechen.) Kadison und Singer hatten gezeigt, dass für Zustände \rho\colon {\mathcal A}\to{\bf C}^n die Erweiterungen nicht immer eindeutig sind, sie hatten aber Eindeutigkeit der Fortsetzung für Zustände \rho\colon {\mathcal A}\to{\bf C} vermutet. Über die Jahrzehnte war dieses Problem zu einem Problem in endlichdimensionalen Vektorräumen (statt dem Hilbert-Raum l2N) reduziert worden. Für jedes ε›0 soll es ein k geben, so dass für jedes n und jede nxn-Matrix T mit verschwindenden Diagonalelementen es eine Aufteilung der ersten n Zahlen in k Mengen Ai gibt mit \Vert P_iTP_i\Vert \le\epsilon \Vert T\Vert für alle i, wobei Pi die Projektion auf den Unterraum ist, der von denjenigen Vektoren der Standardbasis aufgespannt wird, deren Indizes in der Menge A_i\subset\left\{1,\ldots,n\right\} liegen. Die Diskrepanztheorie kam ins Spiel, als Nik Weaver 2004 das Kadison-Singer-Problem umformulierte in das Problem, zu α>0 und Vektoren v1,…,vn mit \Vert v_i\Vert^2\le\alpha und \sum_i\langle v_i,x\rangle^2=1 für alle \Vert x\Vert=1 eine Aufteilung von {1,…,n} in zwei Teilmengen R und B zu finden, so dass \vert \sum_{i\in R}\langle v_i,x\rangle^2-\frac{1}{2}\vert \le 5\sqrt{\alpha} und \vert \sum_{i\in B}\langle v_i,x\rangle^2-\frac{1}{2}\vert \le 5\sqrt{\alpha} für alle \Vert x\Vert=1 gilt. Diese Formulierung konnten Spielman, Marcus und Srivastava 2013 mit elementaren Methoden beweisen.

1 / 2 / 3 / Auf einer Seite lesen
Stichworte: , ,
Mehr

Kommentare (16)

  1. #1 rolak
    4. Februar 2022

    ^^erstaunlich, welch schräge und interessante Problematiken aus einer einzigen, so simpel scheinenden Frage erwachsen…

  2. #2 Bernd Nowotnick
    4. Februar 2022

    Nach meiner Meinung ist das eine geschlossene Berechnung. Die Mitte ist die 1, innen die Null und außen die Unendlichkeit. Bei der physischen Welt entsteht die Zeit als Strömung nach innen, wobei dann der Raum auf Grund einer Strömung nach außen entsteht und dabei der Fluss das Raumintergral des Informationsfeldes, die Kraft das Raumintegral des Wertfeldes, die Energie das Raumintegral des Plasmas, die Wirkung das Raumintegral des Gases, das Gas das Raumintegral der Flüssigkeit, die Flüssigkeit das Raumintegral des Festkörpers, der Festkörper der Raumgratient der Flüssigkeit, die Flüssigkeit der Raumgratient des Gases, das Gas der Raumgratient des Plasmas, die Wirkung der Raumgratient des Wertfeldes die Energie der Raumgratient des Informationsfeldes, die Leistung der Raumgratient des Flusses, der Fluss der Zeitgradient des Informationsfeldes, die Leistung der Zeitgradient des Wertfeldes, die Energie der Zeitgradient des Plasmas, die Wirkung der Zeitgradient des Gases, das Gas der Zeitgradient der Flüssigkeit, die Flüssigkeit der Zeitgradient des Festkörpers, der Festkörper das Zeitintegral der Flüssigkeit, die Flüssigkeit das Zeitintegral des Gases, das Gas das Zeitintegral des Plasmas, die Wirkung das Zeitintegral des Wertfeldes die Energie das Zeitintegral des Informationsfeldes sowie das Informationsfeld das Zeitintegral der Leistung ist. Es bleibt am Ende nur der Weg übrig.

  3. #3 Karl-Heinz
    Graz
    5. Februar 2022

    @Bernd Nowotnick

    Wenn ich deinen Namen lese, dann weiß ich schon im Vorfeld, dass jetzt grober Unsinn kommt.

    Schlussfolgerung:
    A: Der Name “Bernd Nowotnick” taucht auf
    B: Die Antwort ist zu 100% Unsinn
    A → B

    Dann gilt auch: Aus ¬B→ ¬A.
    Mit Worten: Taucht der Name “Bernd Nowotnick” nicht auf, so muss die Antwort nicht unbedingt 100% Unsinn sein.

  4. #4 Karl-Heinz
    Graz
    5. Februar 2022

    Upss: Korrektur
    Dann gilt auch: Aus ¬B→ ¬A.
    Mit Worten:
    Ist die Antwort nicht zu 100% Unsinn, dann stammt die Antwort sicher nicht von “Bernd Nowotnick”.

  5. #5 Quanteder
    6. Februar 2022

    Jeder Unsinn trägt Sinn . . . .. Welcher Sinn könnte dies hier sein? Unwissenheit und Wissen(heit). Jeder kann sich selbst zuordnen, ob er zu den unwissenden oder wissenden Personen zu zählen ist. Wissende Personen grenzen Informationen, welche sich vor ihm darstellen, nicht aus. Sie halten es wie die Mathematik, sie grenzen Informationen ein und grenzen diese nicht aus . . . ..

  6. #6 Karl-Heinz
    Graz
    6. Februar 2022

    @Quanteder

    Ich grenze niemanden aus. Ich stelle nur fest, dass manche Informationen nichts taugen. Ich weiß es klingt hart für jemanden, der gerne weltoffen sein möchte oder vorgibt weltoffen zu sein.

  7. #7 Bernd Nowotnick
    6. Februar 2022

    #6

    Der Weg ist Wissen, steht der Glaube vor dem Abgrund muss er seinen Weg anpassen.

  8. #8 Karl-Heinz
    Graz
    6. Februar 2022

    @Bernd Nowotnick

    Anstatt mir zu erklären, warum #2 kein Unsinn ist, kommst mit der Ansage “Der Weg ist Wissen, steht der Glaube vor dem Abgrund muss er seinen Weg anpassen.”

    Sei mir bitte nicht böse:
    Mein Frage: Was soll das?

  9. #9 Bernd Nowotnick
    6. Februar 2022

    #8

    Gehen wir einen Schritt zurück in die Technik, also zu festen Frequenzen, sagen wir die Elektrotechnik. Da ist der Fluss mit Strom bezeichnet. In der zweiten Stufe der Kraft finden wir die Leistung in W, das Magnetfeld, den Sog, bzw. die Spannung und in der dritten Stufe ist das elektrische Feld, also die Energie in Ws. Bei der vierten Stufe dem Plasma finden wir die Elektronen als Wirkung in Wss, müssen als Verschiebung aber die Positronen mit betrachten. In der fünften Stufe finden wir das Gas in der sechsten Stufe die Flüssigkeit und den Festkörper in der siebenten Stufe und können dabei die Berechnungsmethoden der Elektrotechnik nachvollziehen.

  10. #10 Echt?
    7. Februar 2022

    Beam mich runter Scotty

  11. #11 HD
    8. Februar 2022

    Eine kleine Korrektur: Soweit ich weiß, hieß Erdős mit Vornamen Paul, nicht Pál – so steht es auch im Namen des Quellennachweises für das Bild. Oder ist Pál die ungarische Schreibweise seines Vornamens?

  12. #12 Thilo
    8. Februar 2022

    Ja.

  13. #13 Karl-Heinz
    Graz
    8. Februar 2022

    @HD
    Pál, auch Pål und Pal, ist ein männlicher Vorname sowie ein Familienname. 🙂

    https://de.m.wikipedia.org/wiki/P%C3%A1l

  14. #14 Bernd Nowotnick
    9. Februar 2022

    #10

    Es sind die Kräfte welche erst beide Pole erschaffen – Ich (mir) bin – ein Teil der in Gier immer mehr für mich will und trotzdem immer wieder das Gute erschaffe. Sie propagieren die Illusion, wir seien ein separates vom Universum abgetrenntes Selbst.

  15. #15 Bernd Nowotnick
    9. Februar 2022

    Gehen wir einen Schritt zurück. Wer meint, dass es nichts mit Corona zu tun hat:

    https://www.focus.de/gesundheit/news/news-zur-corona-pandemie-rki-registriert-234-250-corona-neuinfektionen-inzidenz-bei-1450-8_id_26124600.html

    „Immer wieder kommt der Verdacht auf, dass das Institut für Virologie in Wuhan der Ort der Entstehung des Coronavirus sein könnte. Laut Drosten habe das Institut in einem Projekt der US-amerikanischen NGO „Ecohealth Alliance“ sogenannte „Gain-of-Function-Experimente“ durchgeführt.
    Dabei werden Fledermausviren mittels Gentechnik neue Spikeproteine eingebaut. Es habe sich gezeigt, “dass die so konstruierten Viren sich besser vermehren konnten”, sagte Drosten. “Es wurde auch bekannt, dass Pläne zum Einbau von Furinspaltstellen bestanden, aber das sollte in einem amerikanischen Labor gemacht werden, und das Projekt wurde nicht finanziert“, so Drosten.
    Über eine solche Furinspaltstelle verfügt auch das Coronavirus. Das hilft ihm dabei, Atemwegszellen zu befallen. „Das Einfügen einer Furinspaltstelle wäre ein theoretisch denkbares Laborexperiment”, erklärt Dorsten.“

    Im alten Griechenland ging man bei der Lösung von Problemen der Frage nach: Wem nützt es.

  16. #16 Theorema Magnum – Mathlog
    31. Juli 2022

    […] über beschränkte Primzahllücken Die Grunewald-Ash-Vermutung Die Yau-Tian-Donaldson-Vermutung Erdős’ Diskrepanz-Problem Optimalität der E8-Kugelpackung Die Hodge-Riemann-Relationen für Matroide Die Onsager-Vermutung […]