A Hungarian gem

Endre Szemeredi gets Abel Prize 2012 for his fundamental contributions to discrete mathematics and theoretical computer science.

Endre Szemeredi was destined to be a mathematician and that too a towering combinatorialist even though he did not start out as a mathematics student. By being named for the Abel Prize, generally regarded as the Mathematician's Nobel, for the year 2012, he has attained the pinnacle of mathematical achievement. It may be recalled that the Nobel Prize does not cover mathematics. Many mathematicians feel this sort of high recognition to Szemeredi was long overdue.

Instituted in the year 2001 in honour of the Norwegian mathematical wizard Niels Henrik Abel (1802-1829) on his 200th birth anniversary by the Norwegian Academy of Science and Letters, the Abel Prize has been awarded annually since 2003. It is given to mathematicians in recognition of outstanding contributions in the field. The prize carries a cash award of six million Norwegian kroner (NOK), which is about 800,000, or $1 million, similar to the Nobel Prize. Until the Abel Prize was established, the most coveted award in mathematics was the Fields Medal, which is given once in four years at the International Congress of Mathematicians (ICM) to mathematicians not over 40 on January 1. Like the Nobel, the Abel Prize has no restriction on age.

The announcement of the award to this 71-year-old Hungarian, who is with the Alfred Renyi Institute of Mathematics of the Hungarian Academy of Sciences in Budapest and is also an adjunct professor at the Rutgers State University in New Jersey, United States, was made on March 21 in Oslo by the President of the Academy, Nils Christian Stenseth. The award, as the citation says, is for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions in additive number theory and ergodic theory.

Michael Capalbo, a former mathematician from Rutgers who has collaborated with Szemeredi, has been quoted as saying, People think mathematics is a young man's game and once past a certain age you don't come up with any good ideas. I can tell you he has a lot of ideas. Indeed, as Fields medallist W.T. Gowers of Cambridge University, who made a presentation on Szemeredi's work at the announcement ceremony, said, he shows no signs of slowing down and continues to add to his list of over 200 publications.

Szemeredi, in fact, entered the world of mathematics somewhat late. In high school, he has said, he did not study mathematics because his father wanted him to be a doctor. He attended medical school for a year and then worked in a factory for two years. He has been quoted as saying that his interest in mathematics was kindled by his friend in school, who was the tallest guy in class and whom he looked up to, both literally and figuratively. I always listened to him because he was tall, Szemeredi has said. After his factory stint he apparently chanced upon his tall friend who had become a physicist by then. Szemeredi too switched to physics, and it was physics that eventually led him to mathematics.

While a student at Eotvos Lorand University in Budapest, his extraordinary talent in mathematics came to be discovered by Paul Erdos, the well-known Hungarian mathematician who is famous for collaborating with as many as 511 mathematicians around the world on diverse subjects and has mentored several important Hungarian mathematicians of the 20th century. Erdos became Szemeredi's mentor as well. Szemeredi did his PhD in 1970 from Moscow State University under the famous Russian mathematician Israel M. Gelfand.

There is, however, an interesting story about his ending up to work with Gelfand whose areas of specialisation were group theory, representation theory and functional analysis, areas far removed from Szemeredi's own fields of discrete mathematics, specially combinatorics, his contributions to which have now fetched him the Abel Prize. Actually Szemeredi was sent to work with Alexander Gelfond, another well-known Russian mathematician, but he ended up wrongly at Gelfand's doorsteps. But even years of association with Gelfand did not diminish in any way his interest in combinatorics in which he came to make path-breaking contributions. Under circumstances similar to what happened in Szemeredi's early life, a lesser individual would have most likely ended up differently.

Discrete mathematics

What is discrete mathematics? It is the study of structures such as graphs, sequences, permutations and geometric configurations. A continuous structure is that where one can move continuously from one point to another. Real numbers, for example, form a continuous mathematical structure since they vary continuously and smoothly. Or, if one is mathematically modelling fluid flow, then one needs to specify velocities and pressures at various points in the flow path, which too vary smoothly. Discrete structures, on the other hand, involve jumps from one point to another, like, for example, the set of integers, or sequences of 0s and 1s that constitute computer instructions, and one instruction and another differ by flips of 0s and 1s. Graphs constitute important objects of study in discrete mathematics. They are actually an abstract representation of a set of objects where some pairs are connected by links. The objects are denoted by vertices and the links that join some of them are denoted by edges. A road map, for example, is a graph where roads are the edges and intersections are the vertices.

The mathematics of discrete structures forms the foundation of theoretical computer science and information science. Analysis of algorithms in computer science and design of efficient algorithms often rely crucially on insights from discrete mathematics. Communication networks such as the Internet, for example, are best studied using tools of graph theory. Combinatorics can be defined as the study of discrete structures involving counting the structures with given properties, though not all study of discrete structures constitute combinatorics. The combinatorics of discrete structures is also a major component of many areas of pure mathematics such as number theory, probability, algebra, geometry and analysis.

According to Gowers, another characteristic of the subject of combinatorics is that its problems can be stated in a way that is easy to understand. Also, the proofs are often elementary in the sense that the argument does not involve advanced concepts or rely on previously established difficult results, but they are not easy. That is, the proofs can often involve use of elementary mathematics in extremely complicated and sophisticated ways, requiring considerable ingenuity on the part of the mathematician.

Szemeredi revolutionised discrete mathematics by introducing ingenious and novel techniques and by solving many fundamental problems and proving several important theorems. His work, says the citation, has brought combinatorics to the centre stage of mathematics by revealing deep connections to such fields as additive number theory, ergodic theory, theoretical computer science and incidence geometry. The theoretical impact of his work has been a game-changer.

He has been described as a mathematician with exceptional research power and his influence in mathematics has been enormous. The festschrift titled An Irregular Mind, published on the occasion of his 70th birthday in 2010, says in a humorous vein that Szemeredi's unique way of thinking and extraordinary mathematical vision are perhaps due to his brain being wired differently an irregular mind from most mathematicians.

Szemeredi has made deep contributions to problems of a combinatorial nature that arise in theoretical computer science in areas such as data structures, complexity theory, explicit constructions, lower bounds, computational geometry, etc., points out Jaikumar Radhakrishnan, a theoretical computer scientist at the Tata Institute of Fundamental Research (TIFR), who was Szemeredi's first PhD student at Rutgers. Interestingly, for all the impact that his work has had on computer science, Szemeredi has said, I never use computers. That is a little bit contradictory, but that is the truth.

As noted in the citation of the Abel Prize, Jaikumar too observes that Szemeredi belongs to the strong problem-solving tradition of 20th century Hungarian mathematicians whose guiding spirit was Erdos. The approach, says Jaikumar, is characterised by posing problems, going after them with bare hands, building on them to come up with new problems, applying new and old insights, no matter where they come from, to solve them. Many of the combinatorial problems are dealt with not by exact formulae but by parameters, bounds and asymptotics. Szemeredi worked in a milieu of outstanding mathematicians of this school. I believe he thinks of his contributions as part of this culture and that what he did deeply influenced many recent developments in number theory because he happened by chance to work on an important problem.

Szemeredi's Theorem

The most famous result of Szemeredi is his proof in 1975 in the area of additive number theory of what is now called Szemeredi's theorem. This theorem, Gowers points out, is one of the highlights of 20th century mathematics and also forms the basis of a lot of very recent research. The theorem, which is actually a proof of a decades-old conjecture of Erdos and Pal Turan and has to do with arithmetic progression, can be simply stated. But Szemeredi's proof of it was both elementary in the above sense and extremely complicated.

From school mathematics one knows what an arithmetic progression is: it is a sequence of numbers with a constant difference between consecutive numbers in the sequence. An arithmetic progression is determined by its length, difference and initial value. For example, the sequence 12, 19, 26, 33, 40, 47 is an arithmetic progression of length 6, difference 7 and initial value 12. The sequence of integers (or a sub-sequence of it) is also an arithmetic progression with difference 1. In 1921, Pierre Joseph Henry Baudet, a Dutch mathematician, conjectured the following: If one divides the natural numbers 1, 2, 3, ad infinitum into a certain random number of boxes, then there is always at least one box which contains an arithmetic progression of arbitrary length.

The conjecture was proved in 1927 by another Dutch mathematician, Bartel Leendert van der Waerden. The Erdos-Turan Conjecture is actually a stronger version of this. The theorem is best described in lay terms as a one-player game, as Gowers did in his presentation. Suppose one is asked to choose as many numbers between 1 and 10,000 as one can but ensuring that from the numbers chosen one cannot construct an arithmetic progression of length 5. Suppose the numbers chosen included 96, 239, 382, 525 and 668, one would have lost the game because this is 5-term arithmetic progression with difference 143. One will, of course, eventually lose this game because if one keeps going like this for long enough one would have chosen all the numbers between 1 and 10,000 which will include many 5-term arithmetic progressions.

But Szemeredi's theorem makes a stronger statement. Even if one employed the best strategy to avoid a 5-term progression, one would lose long before one got anywhere close to choosing the entire set. In more precise mathematical language, if k is the length of the progression that one is trying to avoid and n is the size of the set of numbers, which is large, the largest number of numbers one can choose without including any k-term progression is a very small fraction of n. The point of the theorem is that, for a given k, there is always some n (which may be huge but it exists) such that if we played the game with n numbers, we will lose by the time we have chosen a tiny fraction of them. Another way of understanding this simply is by colouring natural numbers using only two colours, say red and blue. However, we choose to colour the numbers, it will be seen that a 3-term arithmetic progression can be avoided only up to 8 consecutive integers. A natural number sequence of length 8, coloured as RBRBBRBR for example, does not have a 3-term progression with the same colour. But already with 9 integers, a 3-term progression becomes inevitable.

Of course, we have considered above only two subsets of the set of integers by way of illustration. In the more general case of arbitrary number of subsets of the infinite set of integers, the Erdos-Turan Conjecture is about the property called positive upper density of the subsets and says that any subset that has a strictly positive upper density will contain an arithmetic progression of arbitrary length. In simple and intuitive terms, as R. Balasubramanian, Director of the Institute of Mathematical Sciences (IMSc), Chennai, explains, the theorem asserts that no matter how we choose an infinite set of integers, as long as its size is a strictly positive fraction however small of the infinite set of integers, then such a set will contain arithmetic progressions of any desired length.

In 1953, Klaus Friedrich Roth proved that any subset of the integers with positive upper density contains an arithmetic progression of length 3. In 1969, Szemeredi proved using a difficult combinatorial method that the subset must contain a 4-term arithmetic progression. It was in 1975 that in a landmark paper Szemeredi succeeded in proving the general case that any subset with positive density must contain an arithmetic progression of arbitrary length. For this, Szemeredi was awarded the Leroy P. Steele Prize of the American Mathematical Society (AMS), and the citation said: The solution [of the Erdos-Turan Conjecture] is a true masterpiece of combinatorics, containing new ideas and tools whose impact go well beyond helping to solve a specific hard problem. This result, points out Balasubramanian, tells us that we can find structures like arithmetic progressions in this case in randomly built sets of integers only assuming that their size is not too small.

Mathematical applications

While Szemeredi's theorem does not have any practical applications, its significance lies in the fact that it has found several mathematical applications. A particularly important result that followed from Szemeredi's theorem is due to Ben Green and the Fields medallist Terrence Tao. The Green-Tao theorem states that you can find arbitrarily long arithmetic progressions that consist only of primes. This result does not follow directly from Szemeredi's theorem, but Green and Tao cleverly converted their problem into a form that allowed Szemeredi's theorem to be applied to it.

In fact, the two spent two years analysing all four proofs of Szemeredi's theorem. We took Szemeredi's theorem and goosed it so that it handles primes, Tao said when he was awarded the Fields medal in 2006. To do that, we borrowed from each of the four proofs to build an extended version of Szemeredi's theorem. Every time Ben and I got stuck, there was always an idea from one of the four proofs that we could somehow shoehorn into our argument. The theorem inspired Hillel Furstenberg to develop ergodic theory statistical theory of behaviour of dynamical systems that run for a long time in new directions. He gave a new ergodic-theoretic proof of Szemeredi's theorem, thereby providing an interesting link between questions in discrete mathematics to the theory of dynamical systems. This has opened up the subject of Ergodic Ramsey Theory. There has been a rapid development in this area in recent years, points out Sukumar Adhikari of Harish-Chandra Research Institute, Allahabad.

As Gowers said in his presentation, An important and not sufficiently appreciated aspect of mathematics is that the result you prove is often less interesting than the methods you use to prove it. This tendency is especially pronounced in combinatorics, where open problems often become popular not because we are desperate to know the answers but because they encapsulate some more general difficulty that we feel is holding us back mathematically. When such a problem is solved, the solution often involves the development of new tools that go on to be used in many other contexts. Szemeredi's theorem provides a wonderful illustration of this phenomenon too.

A key step in the proof, now known as the Szemeredi Regularity Lemma, is a structural classification of large graphs. Before the lemma, graphs were thought of as structureless objects because in specifying a graph there are no constraints in deciding whether any two vertices should be joined by an edge or not. But Szemeredi's lemma gives a useful structural description to a completely arbitrary graph. The basic idea, as Gowers has explained, is roughly as follows. Given any graph, there is a way of dividing up its vertices into a small number of sets in such a way that if you take the edges joining any two of these sets, they appear to have been chosen randomly. In other words, every graph is made out of a small number of random-like graphs. That is, a large graph can be well described using a very small amount of data. This is a surprising result and as Jaikumar puts it, the lemma has helped one view seemingly amorphous messy objects as built up of regular structures.

Over the years, this lemma has become a central tool of extremal combinatorics with applications in graph theory and theoretical computer science. Extremal combinatorics studies how large or how small a collection of discrete structures (numbers, graphs, sets, and so on) can be, if it has to satisfy certain conditions. Szemeredi's theorem itself is an example of extremal combinatorics. Thus, extremal graph theory is the study of maximal or minimal graphs which satisfy a certain property. For example, if a graph has n vertices, then how many edges can it have without any three of them forming a triangle?

Regularity Lemma

The Regularity Lemma also has a practical application. One of the elements of artificial intelligence in computer science involves developing computer programs that learn from experience and this is called machine learning. An abstract model that provides a good framework for studying machine learning is called probably approximately correct (PAC) learning. This involves what in computer science is known as property testing algorithm, which seeks answers to purely mathematical questions. Roughly, these questions involve asking whether a particular structure has a certain property or is probably very similar to a structure that does not have this property. Like, for example, whether a graph contains a triangle or differs, if at all, only slightly from a graph with no triangles. For machine learning purposes, property testing algorithm can be executed extremely fast to form a reliable hypothesis about the structure. The tool that allows one to prove that such a hypothesis is probably approximately correct is Szemeredi Regularity Lemma.

The trio of Miklos Ajtai, Janos Komlos and Szemeredi, or AKS for short, have proved several results in combinatorics. One such involves the sorting algorithm, which is an old problem in computer science. A sorting algorithm is designed to order a collection of objects by comparing any two of them and using as few comparisons as possible. In 1945, John von Neumann invented a method known as Merge Sort that requires a number of comparisons that is close to the theoretical minimum. But it remained an open question all these years whether one could devise an algorithm that does the job with this theoretical minimum number of comparisons. AKS solved this problem with a brilliant method of sorting, which is actually a fast parallel algorithm.

Gowers said, Some mathematicians are famous for one or two major theorems. Others are famous for a huge and important body of high-class results. Very occasionally, there is a mathematician who is famous for both. And this is true of Szemeredi. Thus, there is much more to Szemeredi's work than Szemeredi's theorem and Szemeredi's Regularity Lemma. There are a host of results that bear his name. Examples in discrete mathematics include the Szemeredi-Trotter Theorem, the AKS semi-random method, the Erdos-Szemeredi Sum-product Theorem, the Hajnal-Szemeredi Theorem and the Balog-Szemeredi-Gowers Lemma. Examples in theoretical computer science include, besides the AKS sorting network, the Fredman-Komlos-Szemeredi hashing scheme and the seminal Paul-Pippenger-Szemeredi-Trotter Theorem separating deterministic and non-deterministic linear time algorithms, which has implications for the major unsolved P vs NP problem in computer science.

Szemeredi, says Joel Spencer of New York University, has always been motivated by the beauty of mathematical problems. In this way he follows his mentor, the late Hungarian genius Paul Erdos. In my mind Erdos was the spiritual brother of the great Indian mathematician Ramanujan, of whom it was said that he considered the integers as his personal friends. For me, Szemeredi then becomes a nephew of Ramanujan. He is one of those motivated by deep feelings about mathematical structures, beginning with the integers themselves.

On Szemeredi's style of working, Jaikumar speaks from his personal experience with him as his student thus: He is a down-to-earth mathematician. There are no stuffy definitions and high theories in his language, just pictures scratched here and there, and some stray Greek letters as mnemonics. He cannot think sitting in a room. If you ask him a question, he will repeat the question, check that he understood the question correctly. He will apologise for being slow; he will say that he cannot understand anything these days, but that he did understand' the question you posed. Then, he will disappear for a long walk, in the snow and rain outside. When you meet him next, if he has the answer, he will start scratching on the board apologising again and again for his bad handwriting. He will make a claim, and then you must tell him why the claim might be false (that is, what you think the counter example might look like); then he will say, oh! that cannot happen because of this.... Then, you will find another reason why it might be false, and he will tell you why that can't happen either, and this will go on. At some point, you give up. He will then say that everything needs to be checked. He is a careful mathematician.

Nobody who has met him has missed his warmth and humility, Jaikumar adds, speaking about Szemeredi the man. He has been an extremely generous collaborator to dozens of colleagues, especially his students. I have never seen him talk about his achievements. Beyond the circle of colleagues, young and old, he is a private man.

Commenting on what the Abel Prize to Szemeredi means, Jaikumar says, It is impossible for those familiar with his work to think of him without simultaneously recalling the stalwarts of Hungarian mathematics who eagerly embraced and enriched other areas, such as theoretical computer science, especially the theory of algorithms and complexity. Many of them received recognition in various select circles. Yet, for a long time, in the absence of wider acceptance in the mathematical community, they pursued their work on their own internal conviction. In the past decade there has been a greater appreciation of the beauty and the spirit of the problems and methods in discrete mathematics of this kind, as also of the achievements. Those who belong to the Hungarian creed might today imagine that through this award one of their gems has at last found a place in the mathematical crown. It might bring discrete mathematics into focus. In my opinion, this is good for mathematics.