Endre Szemerédi of Rutgers University in New Brunswick, New Jersey, and the Alfréd Rényi Institute of Mathematics in Hungary, has received the 2012 Abel Prize for mathematics, "for his fundamental contributions to discrete mathematics and theoretical computer science," according to a prize committee announcement made today. The 6 million kronor ($1 million) prize has been given out annually by the Norwegian Academy of Science and Letters since 2003. It's named for the early 19th century Norwegian mathematician Niels Henrik Abel, who did groundbreaking work in algebra and analysis despite an early death from tuberculosis at age 27.
Szemerédi's work, mainly in combinatorics (the study of arrangements of finite systems) and number theory, has shown that, as systems made up of discrete components get large—‑think about hyperlinked pages on the World Wide Web—there is structure even when the system is utterly random. Moreover, his work suggests that there are useful aspects of randomness even within systems that are highly structured.
His most famous result is an eponymous theorem establishing the presence of arbitrarily long arithmetic progressions, the epitome of orderliness, within any sequence of integers that doesn't become infinitely sparse. For example, if some mathematical disinfectant killed off 99.99% of the integers at random, the remaining 0.01% would still have arithmetic progressions. Szemerédi's theorem, which he proved in 1975, had been an unsolved problem for decades, first posed by the Hungarian mathematicians Paul Turán and Paul Erdös, who was Szemerédi's mentor. (Erdös, who died in 1996, was known for offering cash prizes for solutions of problems he posed. Szemerédi earned $1000 for solving this one.)
The paper it appeared in "is a real tour de force," says Terence Tao, a mathematician at the University of California, Los Angeles, who was on the committee that chose this year's winner. "When I read it, I felt like I was watching an expert juggler throwing a dozen balls in the air and catching them all flawlessly."
A key step in the proof of Szemerédi's theorem became another eponymous result, known as Szemerédi's regularity lemma. (In mathematics, a "lemma" is usually a minor technical result that acts as a stepping stone in the proof of a main theorem, but occasionally a lemma turns out to be of importance in its own right.) Roughly speaking, the regularity lemma says that any large system can be divided into chunks of roughly equal size that are connected to one another seemingly at random. This permits the analysis of complicated systems without getting bogged down in the fine details of their structure. Among the areas where researchers have applied the regularity lemma is the field of machine learning in artificial intelligence.
In a survey of Szemerédi's work in conjunction with the Abel Prize announcement, mathematician Timothy Gowers of the University of Cambridge in the United Kingdom notes that Szemerédi's contributions go far beyond a single theorem and lemma. "He has published over 200 papers" in a career spanning 5 decades, Gowers says, "and at the age of 71 he shows no signs of slowing down."