Der Abelpreis (mit gut 106 $ der höchstdotierte Mathematikpreis) geht dieses Jahr an Endre Szemeredi.

Der Abelpreis
wird jährlich von der Norwegischen Akademie der Wissenschaften vergeben.

(Er gilt als eine Art Ersatz dafür, daß es keinen Nobelpreis für Mathematik gibt. Über die Gründe, warum Nobel keinen Mathematik-Nobelpreis stiftete, gibt es viele anekdotische Erklärungen, die aber nach allgemeiner Meinung alle in das Reich der Fabel gehören.)

Die Verleihung findet Ende Mai in Oslo statt.

Dieses Jahr wird der Preis an Endre Szemeredi verliehen, dessen Arbeiten oft unter dem Schlagwort structure vs. randomness dargestellt werden.
Sein wohl bekanntester Satz behandelt die Frage: Gibt es in einer zufällig gewählten Menge natürlicher Zahlen beliebig lange arithmetische Folgen? Die (von ihm zuerst mit elementaren Methoden und später von Furstenberg mittels Ergodentheorie bewiesene) Antwort: ja, wenn die Menge positive Dichte hat.
Der Satz wurde später von Green-Tao verbessert auf allgemeinere Mengen der Dichte ~1/log(N) (siehe die Erläuterungen in den Kommentaren unten für die genaue Formulierung), insbesondere gibt es also in der Menge der Primzahlen beliebig lange arithmetische Folgen.

Szemeredi hatte diesen Satz mit Methoden der Graphentheorie beweisen, insbesondere bewies er in diesem Zusammenhang das Szemeredi-Regularitätslemma (“jeder hinreichend große Graph kann in annähernd gleich große Teilmengen zerlegt werden, so daß sich die Kanten zwischen diesen Teilmengen fast zufällig verhalten”). Furstenberg bewies den Satz dann später mittels Ergodentheorie, auch der Beweis des stärkeren Satzes von Green-Tao benutzt die Sprache der Ergodentheorie, aber auch das Szemeredi-Regularitätslemma.

Es gibt viele weitere Sätze von Szemeredi, vor allem in der Graphentheorie.

i-71b41c116a20d5fa44b3454ad363b994-AnIrregularMindBookCoverFairUse.jpg

An irregular mind

Die Begründung des Abelpreiskomitees:

Discrete mathematics is the study of structures such as graphs, sequences, permutations, and geometric configurations. The mathematics of such structures forms the foundation of theoretical computer science and information theory. For instance, communication networks such as the internet can be described and analyzed using the tools of graph theory, and the design of efficient computational algorithms relies crucially on insights from discrete mathematics. The combinatorics of discrete structures is also a major component of many areas of pure mathematics, including number theory, probability, algebra, geometry, and analysis.
Endre Szemerédi has revolutionized discrete mathematics by introducing ingenious and novel techniques, and by solving many fundamental problems. His work has brought combinatorics to the center-stage of mathematics, by revealing its deep connections to such fields as additive number theory, ergodic theory, theoretical computer science, and incidence geometry.
In 1975, Endre Szemerédi first attracted the attention of many mathematicians with his solution of the famous Erdo˝ s-Turán conjecture, showing that in any set of integers with positive density, there are arbitrarily long arithmetic progressions. This was a surprise, since even the case of progressions of lengths 3 or 4 had earlier required substantial effort, by Klaus Roth and by Szemerédi himself, respectively.
A bigger surprise lay ahead. Szemerédi’s proof was a masterpiece of combinatorial reasoning, and was immediately recognized to be of exceptional depth and importance. A key step in the proof, now known as the Szemerédi Regularity Lemma, is a structural classification of large graphs. Over time, this lemma has become a central tool of both graph theory and theoretical computer science, leading to the solution of major problems in property testing, and giving rise to the theory of graph limits.
Still other surprises lay in wait. Beyond its impact on discrete mathematics and additive number theory, Szemerédi’s theorem inspired Hillel Furstenberg to develop ergodic theory in new directions.
Furstenberg gave a new proof of Szemerédi’s theorem by establishing the Multiple Recurrence Theorem in ergodic theory, thereby unexpectedly linking questions in discrete mathematics to the theory of dynamical systems. This fundamental connection led to many further developments, such as the Green-Tao theorem asserting that there are arbitrarily long arithmetic progressions of prime numbers.
Szemerédi has made many additional deep, important, and influential contributions to both discrete mathematics and theoretical computer science. Examples in discrete mathematics include the Szemerédi-Trotter theorem, the Ajtai-Komlós-Szemerédi semi-random method, the Erdo½ s-Szemerédi sum-product theorem, and the Balog-Szemerédi-Gowers lemma. Examples in theoretical computer science include the Ajtai-Komlós-Szemerédi sorting network, the Fredman-Komlós-Szemerédi hashing scheme, and the Paul-Pippenger-Szemerédi-Trotter theorem separating deterministic and non-deterministic linear time.
Szemerédi’s approach to mathematics exemplifies the strong Hungarian problem-solving tradition. Yet, the theoretical impact of his work has been a game-changer.

Informationen zur Vorgeschichte des Abelpreises findet man hier. Die bisherigen Preisträger seit 2003 sind:
2003 Jean-Pierre Serre (Frankreich): Homotopietheorie, Algebraische Geometrie
2004 Michael Atiyah (GB), Isadore Singer (USA): Globale Analysis
2005 Peter Lax (USA): Partielle Differentialgleichungen, Streutheorie
2006 Lennart Carleson (Schweden): Harmonische Analysis, Dynamische Systeme
2007 Srinivasa Varadan (Indien): Wahrscheinlichkeitstheorie, Große Abweichungen
2008 Jacques Tits (Belgien), John Thompson (USA): Gruppentheorie
2009 Michael Gromov (Frankreich): Riemannsche und Symplektische Geometrie, Geometrische Gruppentheorie
2010 John Tate (USA): Algebraische Zahlentheorie, Elliptische Kurven
2011 John Milnor (USA): Differentialtopologie

Kommentare (16)

  1. #1 Uli
    22. März 2012

    Herzlichen Gückwunsch!

    Nur schade, daß ich nicht die Hälfte verstanden habe, und daß, obwohl ich für Mathematik eigentlich ein Faible habe.

    Aber ich habe sebst in der Wikipedia Artikel über mathematische Themen gesehen, wo mir die Augen nach drei Zeilen leicht glasig wurden. Da merkt man erst, wie sehr man als Computer-Spezi doch immer noch ein Mathematik-Laie ist.

  2. #2 volki
    22. März 2012

    @Thilo:

    Der Satz wurde später von Green-Tao verbessert auf Mengen der Dichte ~log(N)/N, insbesondere gibt es also in der Menge der Primzahlen beliebig lange arithmetische Folgen.

    Das ist nicht ganz richtig. Man kann das nur für gewisse Teilmengen dieser Dichte zeigen aber nicht für alle. Green und Tao wollen dies für allgemeine Mengen der Dichte N/log(N)^c für arithmetische Progressionen der Länge 4 zeigen (wobei c als sehr klein zu erwarten sein wird). Jedoch ist das Paper schon seit 6 Jahren angekündigt und noch nicht einmal auf Arxiv erschienen.
    Hier wird z.B. ein schwächeres Resultat bewiesen:
    http://arxiv.org/abs/math.NT/0610604

    Außerdem wirst du N/log(N) meinen sonst wären diese Mengen sehr dünn…

  3. #3 rank zero
    22. März 2012

    Etwas ausführlicher erläutert Tom Sanders den Stand in seinem Referat Zbl 1158.11007. N.B.: Das Profils Sz.s ist zwar noch nicht ganz Erdős-like, aber doch sehr beeindruckend…

  4. #4 Drahnier
    22. März 2012

    Kann mir bitte jemand mit einem konkreten Beispiel den Satz von Szemerédi erläutern. Es ist ja logisch, dass es Mengen geben muß, die arithmetische Folgen enthalten. Aber nicht alle denkbaren Mengen enthalten arthm. Folgen. Das Problem ist dann doch nur, dass man diese Mengen findet, also nicht mit zufälligen Mengen arbeitet. Es geht also doch nur darum, einen Algorhythmus zu finden, der diese Mengen mit arthm. Folgen definiert. Insoweit gibt Szemerédi einen Algorhythmus an. Frage ist jedoch, ob es nicht weitere Algorhythmen gibt, die ebenfalls solchen Mengen mit arithm. Folgen zugrunde liegen.

  5. #5 volki
    23. März 2012

    @drahnier:

    Ok der Satz von Szemeredi sagt, dass für jedes delta und jedes k es ein N gibt, sodass eine Menge S von ganzen Zahlen zwischen 1 und N die delta*N Elemente hat, es eine arithmetische Folge der Länge k gibt.

    z.B. Wähle k=20 und delta=1/100. Dann kann man ein sehr sehr (unverstellbar) großes N wählen. Dann wählt man zufällige Zahlen zwischen 1 und N aus aber nur N/100=N*delta Stück aus. Wenn man jetzt in diesen N/100 ausgesuchten Zahlen nur gründlich genug sucht dann findet man 20 Stück welche eine arithmetische Progression bilden (also aufeinanderfolgende Zahlen den gleichen Abstand haben).

    Das interessante ist, man kann delta>0 noch so klein und k noch so groß wählen, wie man will. Wenn man N nur groß genug wählt, findet man eine arithmetische Folge der vorgeschriebenen Länge k in jeder Menge mit delta*N Zahlen (Menge mit Dichte delta) mit Elementen (ganzzahlig) zwischen 1 und N.

    Ist die Dichte kleiner als eine feste Zahl delta funktioniert das nicht mehr. Nimm z.B delta=1/N^2 und wähle deine Menge als die Zahle 1,2^2=4, 3^2=9, … ,n^2

  6. #6 volki
    23. März 2012

    Oje hier fehlt was:

    Ist die Dichte kleiner als eine feste Zahl delta funktioniert das nicht mehr. Nimm z.B delta=1/N^2 und wähle deine Menge als die Zahle 1,2^2=4, 3^2=9, … ,n^2
    < \blockquote>

    der Satz sollte beendet werden mit:

    “… als die Zahle 1,2^2=4, 3^2=9, … ,n^2 und n^2 kleiner als N dann gibt es keine arithmetische Progression der Länge 3.”

    @all: Wie erzeugt man “kleiner als” Zeichen ohne, dass der Rest des Kommentars verloren geht?

  7. #7 volki
    23. März 2012

    argh! Schon wieder Mist gebaut. Das “Blockquote” falsch beendet. Die Uhrzeit entschuldigt dies hoffentlich 😉

  8. #8 michael
    23. März 2012

    @volki

    guck hier.

  9. #9 Thilo
    23. März 2012

    Danke für die Erläuterungen!

  10. #10 MichiS
    25. März 2012

    @volki + @Drahnier
    auch danke für die prägnate Kurzfassung des Satzes !
    Hier noch ein schönes PDF dazu:
    http://www.uni-due.de/~hx0050/pdf/av.pdf

    Gibt es, kennen Sie eine praktische Anwendung des Satzes zB in Technik oder Informatik ?

  11. #11 volki
    26. März 2012

    @michael: Danke!

    @MichiS: Der Satz von Szemeredi hat keine “praktische” Anwendung (zumindest kenne ich keine). Dies liegt daran, dass die Schranke S für N, ab der es immer eine arithmetische Progression gibt für jede Anwendung viel zu groß ist – bis jetzt, vielleicht kann man S weiter nach unten drücken, wenn man die Beweismethoden verbessert.

    Die Bedeutung des Satzes liegt eher darin, dass später Fürstenberg (Wolfpreis 2007) und auch Gowers (Fieldsmedaillie 1998) einen ergodentheoretischen Beweise gefunden haben und diese Beweismethoden lassen sich auf viele andere Probleme übertragen. Z.B. verwendet Lindenstrauss (Fieldsmedaillie 2010) solche Beweismethoden und hat diese weiter ausgebaut.

  12. #12 MichiS
    26. März 2012

    @volki…ich weiss, es passt nicht zum Abelpreis…:-)… kann’s mir aber nicht versagen, (wo die Gelegenheit so günstig ist) ihnen selbige Fragen nach dem SATZ von VAN DER WAERDEN zu stellen ( von denen ausgehend ich zu Szemerédi’s Satz gefunden habe):

    1. Bitte um eine ähnliche Kurzfassung des VAN DER WAERDEN THEOREMS bezw. Satzes…

    …habe über Wikipedia:
    http://de.wikipedia.org/wiki/Satz_von_Van_der_Waerden

    auch noch ein super-PDF gefunden (LINK: 2. Literatur-Angabe ):
    P. Herwig, M.J.H. Heule, M. van Lambalgen, H. van Maaren: A new method to construct lower bounds for Van der Waerden numbers. The Electronic Journal of Combinatorics 14, 2007. PDF

    2. Gibt es praktische Anwendungen aus diesem Satz zB in Technik oder Informatik ?

    Ein grosses TIA 🙂 !!!!

  13. #13 volki
    26. März 2012

    @MichiS:

    Der Satz von v.d. Waerden passt sehr gut zum Abelpreis, da dieser Satz der Ausgangspunkt war von Szemeredi’s Satz und den ganzen Untersuchungen.

    So der Satz van v.d. Waerden sagt aus habe ich r Farben zur Verfügung und färbe die ersten N Zahlen irgendwie (zufällig) dann gibt es eine arithmetische Folge der Länge l.

    Dieser Satz folgt direkt aus dem Satz von Szemeredi da ja irgendeine Farbe mindestens einen Anteil von 1/r haben muß. Das heißt, man hat eine Teilmenge A (die mit dieser Farbe gefärbt ist) der ersten N Zahlen mit Dichte 1/r. Also nach Szemeredi gibt es eine arithmetische Progression der Länge l in A, falls nur N groß genug gewählt war.

    Der Satz von Szemeredi ist aber viel schwerer zu beweisen als der Satz von v.d. Waerden da man beim v.d. Waerdenschen Satz nicht eine Farbe fixiert hat, mit der die arithmetische Progression eingefärbt ist. Um es salopp zu formieleren: Man kann in ungünstigen Fällen die Farbe wechseln, was den Beweis wesentlich vereinfacht.

    Ich gehe auch aus, dass für Anwendungen die Schranken viel zu groß sind, um für technische Anwendungen brauchbar zu sein. Für den Satz von v.d. Waerden kenne ich aber Anwendungen für Diophantische Gleichungen (Gleichungen für die nur ganzzahlige Lösungen akzeptiert werden) bzw. in der algebraischen Zahlentheorie. Ich gehe aber davon aus, dass du nicht solche Anwendungen meinst. Ich habe morgen bessere Möglichkeiten zu Anwendungen der Sätze zu suchen und werde mich evt. morgen nocheinmal melden, falls ich etwas gefunden habe.

  14. #14 volki
    27. März 2012

    Also nach kurzer Recherche: Der Satz von Szemeredi wurde seit 2000 ca. in 150 Fachartikeln (das ist ziemlich viel) zitiert. Ich habe natürlich nicht alle genau angesehen aber beim überfliegen ist mir keines aufgefallen, dass eine technische Anwendung bietet. Die meisten Anwendungen kamen aus der additiven Zahlentheorie (wie z.B. der Satz von Green und Tao, der im Artikel zitiert wird).

    Aber man kann anscheinend die Beweismehtode von Szemeredi zu seinem Satz sehr gut in der Graphentheorie und Ramseytheorie anwenden. Da ich mich in den beiden Gebieten nicht wirklich gut auskenne, kann ich nicht beurteilen wie praxisnahe die Anwendungen sind. Zumindest ist Graphentheorie oft praxisnahe besonders in Blick auf Optimierungsprobleme, aber ob dort die Methoden von Szemeredi eine Rolle spielen???

  15. #15 MichiS
    29. März 2012

    @volki…nochmals DANKE für deine konzisen, konsistenten, für mich wieder sehr anschaulichen Antworten zu den beiden Sätzen…frau/man/du sollte diese in den entsprechenden beiden Wikipedia-Artikel als ABSTRACT einfügen, oder ev. einen LINK zu diesem Blog + VOLKI-Kommentaren ???

    …besonders hilfreich war mir: “färbe die ersten N Zahlen IRGENDWIE (ZUFÄLLIG) dann “….dort steckt der Pfeffer drin mit der Farben-Fakultät + der kombintorischen Belegung der leeren Plätze… ???????

    Ein Mathe-Pädagoge ( http://www.spektrum.de/mathekalender ) mailte mir:

    ZITAT: ” natürlich hat mir der Satz von van der Waerden keine Ruhe gelassen …
    Das Beispiel in Wikipedia hat mich aber zunächst einmal abgelenkt (und in die Irre geführt).

    Der Satz besagt salopp, dass es – wenn man eine Reihe von hintereinander liegenden Feldern färbt – immer ein Muster gibt. Der Satz von van der Waerden gibt an, dass es eine Mindestzahl dafür geben muss, wie lang eine solche Reihe ist, damit mindestens ein Muster aus 3, 4, … Feldern ergibt.

    Konkrete Beispiele:
    – Wenn man 9 hintereinander liegende Felder mit zwei Farben färbt, dann findet man bei mindestens einer der beiden Farben ein Muster aus 3 Feldern, das darin besteht, dass das mittlere der drei Felder gleich weit von den beiden äußeren Feldern entfernt liegt.
    – Wenn man 35 hintereinander liegende Felder mit zwei Farben färbt, dann findet man bei mindestens einer der beiden Farben ein Muster aus 4 Feldern, das darin besteht, dass die Abstände der vier Felder untereinander gleich groß sind.
    – Wenn man 27 hintereinander liegende Felder mit drei Farben färbt, dann findet man bei mindestens einer der drei Farben ein Muster aus 3 Feldern, das darin besteht, dass das mittlere der drei Felder gleich weit von den beiden äußeren Feldern entfernt liegt.”

    und:
    “ich habe keine Anwendung im Blick, aber ich habe ja bisher nur versucht zu verstehen, was überhaupt die v.d.Waerden-Zahlen sind. Was ich verstanden habe, ist, dass es auch im Chaos gewisse Regelmässigkeiten gibt, und das finde ich erstaunlich genug …”

    @THILO…gibt es bei dir einen Blog über die Diophantische Gleichungen ?

    ..auch hast du Fast versprochen, einmal etwas über RAMSEYTHEORIE zu bloggen… :-))) http://www.scienceblogs.de/mathlog/2011/10/topologie-von-flachen-clxxxix.php

  16. #16 Thilo
    29. März 2012

    Huch, wenn man sich ernsthaft mit diophantischen Gleichungen befassen will, braucht man so ziemlich alles, was es heute an mathematischer Theorie gibt, Stichwort Arakelov-Theorie.

    (Ausser natuerlich man interessiert sich nur fuer lineare Gleichungen, das ist dann wirklich elementare Zahlentheorie.)

    Mit der Ramsey-Theorie, das behalte ich mal im Hinterkopf.