# Endre Szemerédi

### Quick Info

Budapest, Hungary

**Endre Szemerédi**is a Hungarian-born American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science.

### Biography

**Endre Szemerédi**was born during World War II and his mother died when he was eight years old. He had two brothers but the three boys were all sent to different boarding schools for orphans. He explains in [14] how mathematics proved useful to him in elementary school:-

... when I was in elementary school, I was very short and weak and the stronger guys would beat me up. So I had to find somebody to protect me. I was kind of lucky, since the strongest guy in the class did not understand anything about mathematics. He could never solve the homework exercises, let alone pass the exam. So I solved the homework exercises for him and I sat next to him at the exam. Of course, we cheated and he passed the exam. But he was an honest person and he always protected me afterwards from the other big guys so I was safe. Hence my early interest in mathematics was driven more by necessity and self-interest than by anything else. In elementary school I worked a lot with mathematics but only on that level, solving elementary school exercises.He did not specialise in mathematics at secondary school because his father wanted him to become a medical doctor. This was because, at this time, the medical profession was thought to be that of the highest status and best paid. Therefore he studied biology at school and, after graduating, entered medical school.

Szemerédi only spent six months at the medical school but he dropped out before the end of the first semester. He said [14]:-

I realized that, for several reasons, it was not for me.The main reasons were [16]:-

I was not sure I could do work bearing such responsibility. You also had to study a lot, which I wasn't good at.Not knowing what was right for him, he took a job as a factory-hand in a machine-making factory run by the Precision Mechanics Corporation. He spent almost two years in this job before a chance event led to him becoming a mathematician.

At high school his best friend had been Gábor Ellmann who had been by far the best mathematician in his class. Ellmann had begun his studies of mathematics and physics at Eötvös Loránd University in Budapest in 1958. One day Szemerédi was walking through the centre of Budapest when he saw Ellmann and went to chat to him. Ellmann had been going to meet his girlfriend but, as he was fifteen minutes late, she had not waited for him. Szemerédi and Ellmann chatted and, naturally, Ellmann asked Szemerédi what he was doing. When he heard about his factory job, Ellmann told Szemerédi that he should go to Eötvös Loránd University and study mathematics. Not only was this Ellmann's opinion but, he said, he knew that their high school mathematics teacher Sándor Bende had always thought that Szemerédi should have studied mathematics. Szemerédi had always respected his friend's advice and so he did as suggested and entered Eötvös Loránd University in 1960.

In his first year at university, academic year 1960-61, Szemerédi took mathematics and physics courses with the eventual aim of becoming a high school teacher. He did not find the courses that he attended at all stimulating but continued into his second year. It was at that time that things changed dramatically for Szemerédi and the person who brought about that change was Paul Turán [16]:-

Turán gave a wonderful, all-year comprehensive course on number theory.He describes how Turán's

*course changed his ambitions in [14]:-*

His lectures were perfect. Somehow he could speak to all different kinds of students, from the less good ones to the good ones. I was so impressed with these lectures that I decided I would like to be a mathematician.While an undergraduate, Szemerédi collaborated with two outstanding young mathematicians András Sárközi and János Komlós. András Sárközi (born in Budapest in 1941) was a student at Eötvös Loránd University from 1959 to 1963. He then became a Research Fellow in the Department of Algebra and Number Theory at Eötvös Loránd. János Komlós (born in Budapest in 1942) was also a student at Eötvös Loránd University. He obtained his doctorate in 1967 having been advised by Alfréd Rényi. Szemerédi graduated with a Master's Degree from Eötvös Loránd University in 1965. Then, having already had three papers accepted for publication, he joined the Mathematical Research Institute of the Hungarian Academy of Sciences. These three papers were (with János Komlós and András Sárközi)

*On sums of powers of complex numbers*(1964), (with András Sárközi)

*Über ein Problem von Erdős und Moser*(1965), and (with András Sárközi)

*On the sequence of squares*(1965).

At the Mathematical Research Institute, Szemerédi began to collaborate with Paul Erdős who was a frequent visitor. By this time Erdős had no fixed position but went from one university to another around the world. However, he visited Budapest frequently since his mother continued to live in Hungary. Szemerédi said [14]:-

Paul Erdős had many problems, conjectures. Some of them were not so hard, but the others were extremely difficult. Fortunately or unfortunately the solution to many of his problems required only elementary methods. Of course quite often the proofs using only elementary methods are not simple because one may have to put together basic ingredients in extremely complicated and sophisticated ways. Knowing that I had a very limited knowledge, I was very happy that Paul Erdős was willing to work with me. With him and a fellow mathematician András Sárközi we wrote a large number of papers on number theory.In fact Szemerédi's first paper with Erdős also included Andras Sárközi as a co-author. It was the paper

*On divisibility properties of sequences of integers*(1966). Szemerédi went on to write many (around 30) joint papers with Erdős but, in fact, this number was well beaten by his other co-author from these early days, Andras Sárközi, who has the record of the most joint papers with Erdős (around 50). For the impressive work he had done up to this time Szemerédi was awarded the Grünwald Prize in 1967 by the János Bolyai Mathematical Society, and he received the prize again in the following year. This prize, named for Géza Grünwald (1910-1943) was awarded to outstanding young researchers.

At this stage Szemerédi did not have a doctorate and, given that Hungary now had strong links with Russia and Alexander Gelfond was a world leading number theorist, Szemerédi applied to do research in Moscow with Gelfond as his thesis advisor. However, an unfortunate spelling error (an "a" instead of an "o") meant that when he arrived in Moscow in 1967 he discovered that he had been assigned to be Israil Moiseevic Gelfand's student [14]:-

I realised immediately that this was not for me, and Gelfand also realized it and advised me not to do mathematics anymore, telling me: "Just try to find another profession; there are plenty in the world where you may be successful." I was twenty-seven years old at the time, and he had all these star students aged around twenty, and twenty-seven was considered old!Gelfand's type of mathematics did not suit Szemerédi at all but he did not want to give up and return to Hungary as a failure. He did have a piece of luck, however, for around the end of his first year as a doctoral student in Russia, there was a conference in Debrecen in Hungary which Gelfond attended. Szemerédi, as a Hungarian student who could speak Russian, was assigned to look after him and show him round. Once Gelfond heard of the error that had occurred, he said that when he returned to Moscow he would arrange for Szemerédi to become his student. Sadly, this was not to be since Gelfond died two months after returning to Moscow. Szemerédi continued as Gelfand's student, but was allowed to write his thesis on combinatorics. He had to take other examinations too and was examined by Sergei Bernstein on two exercises from Alexander Kirillov's publications on representation theory. Sergei Bernstein [14]:-

... found the error in the solution, but he said that it was the effort that I had put into it that was important rather than the result, and he let me pass the exam.After submitting his thesis, Szemerédi was awarded a candidate's degree (equivalent to a Ph.D.) from Moscow State University in 1970. Back in the Institute of Mathematics of the Hungarian Academy of Sciences, Szemerédi was awarded their Alfréd Rényi Prize in 1973 which was an annual award to recognise outstanding performance in mathematical research during the previous five years. By 1973 Szemerédi had published over 30 papers and, two years later, in 1975, he published a highly significant result which is now known as Szemerédi's Theorem. This result had been conjectured in 1936 in the paper

*On some sequences of integers*by Erdős and Paul Turán. Szemerédi's Theorem states that in any set of integers with positive density, there are arbitrarily long arithmetic progressions. Here is a precise statement of Szemerédi's Theorem:

For every positive integer $k$ and every $1 ≥ d > 0$ there exists an integer $N$ such that every subset $A$ contained in $\{1, 2, ..., N\}$ of size at least $dN$ contains an arithmetic progression of length $k$.

Tim Gowers writes [8]:-
This theorem is one of the highlights of twentieth-century mathematics, but it also lies at the heart of a great deal of very recent research. He also gave us Szemerédi's regularity lemma, a result that originated in the proof of Szemerédi's theorem but went on to become a major tool in extremal combinatorics.Details of these remarkable achievements are also given in [4]:-

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 continued to receive prizes for his outstanding work. The Society for Industrial and Applied Mathematics awarded him their Pólya Prize for Achievement in 1975 and, in 1979, he received the Prize of the Hungarian Academy of Sciences. In 1982 he was elected as a Corresponding Member of the Hungarian Academy of Sciences and became a full member in 1987. In 1986 Szemerédi moved to the United States when he was appointed State of New Jersey Professor of Computer Science at Rutgers University. However, he continued to hold his professorship at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences in Budapest. In addition to continuing to hold these two positions, Szemerédi held several visiting professorships: Stanford University, 1974; McGill University, 1980; University of Southern California, 1981-1983; University of Chicago, 1985-1986; Fairchild Distinguished Scholar, California Institute of Technology, 1987-1988; Aisenstadt Chair at Centre de Recherche Mathématique in Montreal, 2003; Institute for Advanced Study, Princeton, 2007-2008 and 2009-2010; and Eisenbud Professor, Mathematical Sciences Research Institute, Berkeley, 2008.

After the prizes we have mentioned above, Szemerédi was awarded: the Leroy P Steele Prize of the American Mathematical Society for Seminal Contribution to Research, 2008:-

... for his paper "On sets of integers containing no k elements in arithmetic progression";He won the Rolf Schock Prize in Mathematics decided by the Royal Swedish Academy of Sciences, 2008; the DeLong Lecture Series, University of Colorado, 2010; the Abel Prize, 2012 [4]:-

... 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;He received the George Washington Prize, from the American Hungarian Foundation, at a dinner held at the Waldorf Astoria Hotel, New York City on 14 November 2012.

Another honour given to Szemerédi is described in [12]:-

In 2010, on the occasion of Szemerédi's 70th birthday, the Alfréd Rényi Institute of Mathematics and the János Bolyai Mathematical Society organized a conference in Budapest to celebrate his achievements. In the book, 'An Irregular Mind', published prior to the conference, it is stated that "Szemerédi has an 'irregular mind'; his brain is wired differently than for most mathematicians. Many of us admire his unique way of thinking, his extraordinary vision."Also in 2010 Szemerédi was awarded an honorary doctorate by the Charles University of Prague.

Summing up Szemerédi's achievements up to 2012, Tim Gowers writes [8]:-

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. No account of Szemerédi's work would be complete without a discussion of Szemerédi's theorem and Szemerédi's regularity lemma. However, there is much more to Szemerédi than just these two theorems. He has published over 200 papers, as I mentioned at the beginning, and at the age of 71 he shows no signs of slowing down.Szemerédi claims in [16] to be a professor of computer science who does not know how to use a computer:-

I don't know computers, despite the fact that I work at the Department of Computer Science at Rutgers University. I can prove that my wife answers all my emails. I read them, but I don't know how to use the calculator - I mean computer, I just sometimes call it a calculator. [I don't learn to use a computer because] I'm just simply too stupid for it, I don't understand the whole thing. I understand the internet, that's just a graph, I can model it. But the computer, programming languages, how to search for information, I don't know. I'm also incompetent with cameras, I never learned how to take pictures. And I can't turn the DVD player on, I am helpless if my wife doesn't start the movie I want to watch, or one of my grandchildren doesn't come over to help me out.In [16] Szemerédi describes some of his hobbies:-

I used to love to take walks, but since I've been having hip problems, that is more difficult. I play tennis once a week, but with a trainer who hits the ball so that it bounces right in front of me; I don't even have to move. Two months ago I started playing ping pong. I watch movies with my family, we go to the theatre, I watch any kind of sport on TV. If you ask me about that, I can tell you anything: I have been following sports for decades. Soccer, Formula 1, basketball, even seemingly boring sports like baseball or football. Tennis too, of course. I can't play tennis well, but when the game starts, I see immediately what Nadal's strategy is. You don't have to be a mathematician to do that, only a sports fanatic.Szemerédi is married to Anna Kepes (born 1945); they have five children. Anna Kepes Szemerédi edited the book

*Art in the Life of Mathematicians*(2015). A number of leading mathematicians contributed their thoughts on art, painting, music, dance, photography etc. for this book. Anna organised an exhibition "Art in the World of Mathematicians" for her husband's 70th birthday and the book grew out of the exhibition.

Let us end by quoting Michael Littman, chairman of the Department of Computer Science at Rutgers University [11]:-

Mathematicians are people, too. Some are arrogant and obnoxious. Some are truly humane. Szemerédi is a sweet, sweet man. He has these warm smiling eyes, a nice calm way about him. He's very magnanimous, very generous. He doesn't think he's the only one who works in this field in the world.

### References (show)

- I Bárány and J Solymosi (eds.),
*An Irregular Mind. Szemerédi is 70*(Bolyai Society Mathematical Studies Springer, 2010). - Biography, Endre Szemerédi, The Abel Prize Laureate 2012, The Abel Prize (2012). http://www.abelprize.no/c54147/seksjon/vis.html?tid=54148&strukt_tid=54147
- S Chand and R C Parida, An 'Irregular Mind' wins the Abel Prize,
*Science Reporter*(February 2013), 16-17. - Citation, Endre Szemerédi, The Abel Prize Laureate 2012, The Abel Prize (2012). http://www.abelprize.no/c54147/seksjon/vis.html?tid=54148&strukt_tid=54147
- Curriculum Vitae for Endre Szemerédi, in
*Helge Holden and Ragni Piene (eds.), The Abel Prize 2008-2012*(Springer, Heidelberg-New York-Dordrecht-London, 2014), 507-508. - Endre Szemerédi,
*University of Heidelberg*. http://www.heidelberg-laureate-forum.org/blog/laureate/endre-szemeredi/ - W T Gowers, The work of Endre Szemerédi, in
*Helge Holden and Ragni Piene (eds.), The Abel Prize 2008-2012*(Springer, Heidelberg-New York-Dordrecht-London, 2014), 451-493. - W T Gowers, The work of Endre Szemerédi, Endre Szemerédi, The Abel Prize Laureate 2012, The Abel Prize (2012). http://www.abelprize.no/c54147/seksjon/vis.html?tid=54148&strukt_tid=54147
- Hungarian-American Endre Szemerédi named Abel Prize winner,
*Norwegian Academy of Science and Letters*. http://www.abelprize.no/nyheter/vis.html?tid=54138 - List of Publications for Endre Szemerédi, in
*Helge Holden and Ragni Piene (eds.), The Abel Prize 2008-2012*(Springer, Heidelberg-New York-Dordrecht-London, 2014), 495-506. - A E Nutt, Rutgers math professor's discovery earns prestigious award, $1M prize, The Star-Ledger,
*nj.com*(22 March 2012). http://www.nj.com/news/index.ssf/2012/03/rutgers_math_professors_discov.html - Press Release, Endre Szemerédi, The Abel Prize Laureate 2012, The Abel Prize (2012). http://www.abelprize.no/c54147/seksjon/vis.html?tid=54148&strukt_tid=54147
- R Ramachandran, Hungarian mathematician Endre Szemerédi gets 2012 Abel Prize,
*The Hindu*(22 March 1012). - M Raussen and C Skau, Interview with Endre Szemerédi,
*Notices Amer. Math. Soc.***60**(2) (2013), 221-231. - M Raussen and C Skau, Interview with Endre Szemerédi,
*European Mathematical Society Newsletter***85**(September 2012), 39-49. - G Stockert, Interview with Abel Prize Winner Endre Szemeredi, www.index.hu
- E Szemerédi, Autobiography, in Helge Holden and Ragni Piene (eds.), The Abel Prize 2008-2012 (Springer, Heidelberg-New York-Dordrecht-London, 2014).

### Additional Resources (show)

Other websites about Endre Szemerédi:

### Honours (show)

Honours awarded to Endre Szemerédi

Written by J J O'Connor and E F Robertson

Last Update April 2016

Last Update April 2016