“for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory.”
Endre Szemerédi will receive the Abel Prize from His Majesty King Harald at an award ceremony in Oslo on 22 May.
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.
The Abel Prize
The Abel Prize is an international prize for outstanding scientific work in
the field of mathematics, including mathematical aspects of computer science, mathematical physics, probability, numerical analysis and scientific computing, statistics, and also applications of mathematics in the sciences.
The prize is meant to recognize contributions of extraordinary depth and influence to the mathematical sciences. Such work may have resolved fundamental problems, created powerful new techniques, introduced unifying principles or opened up major new fields of research. The intent is to award prizes over the course of time in a broad range of fields within the mathematical sciences.
The Niels Henrik Abel Memorial Fund was established by the Norwegian Government in 2002 at the bicentennial of the great Norwegian mathematician’s birth. The return of the Fund is allocated to the prize and several related activities, such as the Abel Lectures and the Abel Symposia. An annual grant is given to the International Mathematical Union’s Commission for Developing Countries. Part of the grant is for the Ramanujan Prize for young mathematicians from developing countries.
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.