The beauty of an irregular mind

Here’s the news story on this year’s Abel Prize that I’ve just written for Nature. You’ve always got to take a deep breath before diving into the Abel. But it is fun to attempt it.
___________________________________________________________

Maths prize awarded for elucidating the links between numbers and information.

An ‘irregular mind’ is what has won this year’s Abel Prize, one of the most prestigious awards in mathematics, for Endre Szemerédi of the Alfred Rényi Institute of Mathematics in Budapest, Hungary.

This is how Szemerédi was described in a book published two years ago to mark his 70th birthday, which added that “his brain is wired differently than for most mathematicians.”

Szemerédi has been awarded the prize, worth 6m Norwegian krone (about US$1m), “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”, according to the Norwegian Academy of Science and Letters, which instituted the prize as a kind of ‘mathematics Nobel’ in 2003.

Mathematician Timothy Gowers of Cambridge University, who has worked some of the same areas as Szemerédi, says that he has “absolutely no doubt that the award is extremely appropriate.”

Nils Stenseth, president of the Norwegian Academy of Science, who announced the award today, says that Szemerédi’s work shows how research that is purely curiosity-driven can turn out to have important practical applications. “Szemerédi’s work supplies some of the basis for the whole development of informatics and the internet”, he says, “He showed how number theory can be used to organize large amounts of information in efficient ways.”

Discrete mathematics deals with mathematical structures that are made up of discrete entities rather than smoothly varying ones: for example, integers, graphs (networks), permutations and logic operations. Crudely speaking, it entails a kind of digital rather than analogue maths, which helps to explain its relationship to aspects of computer theory.

Szemerédi was spotted and mentored by another Hungarian pioneer in this field, Paul Erdös, who is widely regarded as one of the greatest mathematicians of the 20th century – even though Szemerédi began his training not in maths at all, but at medical school.

One of his first successes was a proof of a conjecture made in 1936 by Erdös and his colleague Paul Turán concerning the properties of integers. They aimed to establish criteria for whether a series of integers contains arithmetic progressions – sequences of integers that differ by the same amount, such as 3, 6, 9…

In 1975 Szeremédi showed that subsets of any large enough string of integers must contain arithmetic progressions of almost any length [1]. In other words, if you had to pick, say, 1 percent of all the numbers between 1 and some very large number N, you can’t avoid selecting some arithmetic progressions. This was the Erdös-Túran conjecture, now supplanted by Szemerédi’s theorem.

The result connected work on number theory to graph theory, the mathematics of networks of connected points, which Erdös had also studied. The relationship between graphs and permutations of numbers is most famously revealed by the four-colour theorem, which states that it is possible to colour any map (considered as a network of boundaries) with four colours such that no two regions with the same colour share a border. The problem of arithmetic progressions can be considered analogous if one considers giving numbers in a progression the same colour.

Meanwhile, relationships between number sequences become relevant to computer science via so-called sorting networks, which are hypothetical networks of wires, like parallel train tracks, that sort strings of numbers into numerical sequence by making pairwise comparisons and then shunting them from one wire to another. Szemerédi and his Hungarian collaborators Miklós Ajtai and Janós Komlós discovered an optimal sorting network for parallel processing in 1983 [2], one of several of Szemerédi’s contributions to theoretical computer science.

When mathematicians discuss Szemerédi’s work, the word ‘deep’ often emerges – a reflection of the connections it often makes between apparently different fields. “He shows the advantages of working on a whole spectrum of problems”, says Stenseth.

For example, Szemerédi’s theorem brings number theory in contact with the theory of dynamical systems: physical systems that evolve in time, such as a pendulum or a solar system. As Israeli-American mathematician Hillel Furstenberg demonstrated soon after the theorem was published [3], it can be derived in a different way by considering how often a dynamical system returns to a particular state: an aspect of so-called ergodic behaviour, which relates to how thoroughly a dynamical system explores the space of possible states available to it.

Gowers says that many of Szemerédi’s results, including his celebrated theorem, are significantly not so much for what they prove but because of the fertile ideas developed in the course of the proof. For example, Szemerédi’s theorem made use of another of his key results, called the Szemerédi regularity lemma, which has proved central to the analysis of certain types of graphs.


References
1. E. Szemerédi, "On sets of integers containing no k elements in arithmetic progression", Acta Arithmetica 27: 199–245 (1975).

2. M. Ajtai, J. Komlós & E. Szemerédi, "An O(n log n) sorting network", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1–9 (1983).

3. H. Fürstenberg, "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", J. D’Analyse Math. 31: 204–256 (1977).