Autobiography

Abstract

This article is an autobiographical account of how I became a mathematician starting medical school, working at a factory. Followed by a very brief summary of how a failure helped me to find my real subject on which I have been working for more than 45 years.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Unlike most mathematicians I did not start to study to be a mathematician. I was born in 1940 in Budapest, Hungary. I lost my mother when I was 8 years old. My two brothers and I were sent to different boarding schools for orphans. It was a few years after WWII.

I have always liked mathematics, and it actually helped me to survive in a way. I was very short and weak, and the strong tall guys would beat me up. I was kind of lucky, since the physically strongest guy was mathematically very weak. He could never solve his homework exercises. So I solved them for him even at the exams. He was an honest person, he always protected me. So mathematics and in return served my interest. All this happened in elementary school.

In high school I was good at mathematics, but never took part in competitions. For my father’s request I was preparing to be a physician and I studied biology. At this time this was the most recognized profession in Hungary.

My education was not the usual education you get in Hungary if you want to be a mathematician. There are a few extremely good highschools concentrating in mathematics, both in Budapest and in the country side.

After a few months at medical school I realized that it was not for me and not knowing what exactly would suit me I went to work in a machine making factory. These two years were actually a good experience for me. We had to finish our work on time even if we felt that it was very monotonous. As a mathematician I can appreciate now that I can work on things that I like.

Once one of my best friends, Gabor Ellmann, who attended the university to become a mathematics and physics teacher, suggested that I try to go to the university to study the same thing. So I tried. At that time in Hungary you studied mathematics and physics for two years, in the third year if you decided to be a mathematician and were among the 15 best, you were able to specialize in mathematics. The others followed with math and physics plus pedagogy and psychology to become a mathematics and physics teacher in a high school.

After being admitted to the Eötvös Loránd University in 1960, and attending Professor Paul Turán’s lecture series on number theory. I consider Professor Turán to be the one who actually helped me to decide to become a mathematician and he still is one of my icons. I never worked with him, I have only listened to his lectures and sometimes went to his seminars.

When I had finished at the university I was hired at the Mathematical Research Institute (later Rényi Alfréd Institute) of the Hungarian Academy of Sciences.

At that time Paul Erdős, the great Hungarian mathematician, often visited Hungary. His mother lived in Budapest. His main area was discrete mathematics. This included a lot of things. Among others elementary number theory, graph theory, random graph theory and so on. Paul Erdős and Alfred Renyi are the founders of random graph theory. 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 Andras Sarkozy we wrote a large number of papers on number theory. Then I decided that I would do something alone. My first try ended up in failure. Anyway I am going to tell it, because it is very closely related with my later works, and also it shows that a failure—even an embarrassing one—can be helpful later. The story is the following. I tried to prove that in a long arithmetic progression it is not possible that a positive percentage of the elements of the arithmetic progression are squares. In order to prove it, I took it for granted that if you have a positive percentage of the integers, then it contains an arithmetic progression of length 4. I proved that if you have an arithmetic progression of length 4, then not all of them can be squares. If you put these results together, you prove what you wanted. I was very proud of ‘my result’. I showed the proof to Paul Erdős. Then he told me that there were some slight problems with the “proof”. The first one was that I assumed something which had not been proved yet at that time, namely that any set of a positive percentage of the integers contains an arithmetic progression of length 4. But this was still OK. The second one was really shameful. Erdős told me that the other thing, stating that there are no four squares that form an arithmetic progression, was proved by Euler, already 250 years earlier. I felt that I must correct this mistake, because Erdős was my other icon and mentor.

Still at the Rényi Institute I started to work on the arithmetic progression problem. Van der Waerden proved his famous theorem, stating that if you divide the integers into finitely many classes, then some class contains arbitrarily long arithmetic progressions. Then Erdős and Turán conjectured in 1936 that the important thing is that the set is dense enough. If you have a positive proportion of the integers, then you have already long arithmetic progressions. More precisely speaking, for every d>0 and every positive integer k there exists a number n=n(d,n) such that every subset of the integers {1,2,…,n}, n>n(d,k) of cardinality dn contains an arithmetic progression of length k. In 1953 Roth provided a beautiful proof, using harmonic analytic methods, that the conjecture is true for k=3. He even proved that among at least n/loglogn integers there was always an arithmetic progression of length 3. Actually, one of my favorite mathematicians is K.F. Roth. When I first went abroad in 1967, I met him and read his proof. I knew very little about harmonic analysis, so I tried to use elementary methods. First I gave a very simple high school proof for k=3. Then I proved it for k=4. In 1967 Paul Erdős arranged for me an invitation to the University of Nottingham. There I was supposed to give a lecture about my proof. My English was practically non-existing. So I just drew some pictures, and Peter Elliot and Edward Wirsing, both number theorists, based on these pictures and my very bad English, wrote down the proof. I am very grateful for their great help.

In 1968 I went to Moscow to be a PhD student of Gelfond, a well known number theorist. By some unfortunate misspelling of the names I ended up with I.M. Gelfand who was one of the greatest mathematicians of the last century, but his area was very far from my expertise and soon I realized that I can not learn that kind of mathematics. I was lucky that Gelfond visited Budapest, and I, as a student studying in Moscow, was supposed to be his guide. He was a very nice, warm person. He agreed to arrange that I would be his student. Soon after his return to Moscow he tragically died.

András Hajnal, the well known logician and combinatorialist spent half a year in Moscow in 1969. We worked together and proved an important conjecture of Erdős. He was working at his desk while I worked walking in the woods. Considering that the Russian winter usually is pretty harsh, my working method may not have been an optimal one. I.M. Gelfand was very generous and agreed that this result was good enough for a PhD thesis. Later our result generated a lot of activities in graph packing.

In 1973 I proved the Erdős–Turán conjecture. My good friend András Hajnal helped me to write up the paper. Or better, say he listened to my explanations and then wrote it up.

Endre Szemerédi, 1977

The Szemerédi family

After my proof many different proofs were found. Furstenberg gave an ergodic theoretical proof. His method is much deeper and much more powerful than my elementary method, and could be generalized into the multidimensional setting. He and Katznelson could prove in 1978 a multidimensional analogue, and they could finally prove in 1991 the density version of the Hales–Jewett theorem.

Timothy Gowers gave a much, much better bound than what I had. Even more importantly, he invented many fundamental methods which completely changed the landscape. We cannot overestimate the influence of his paper. Gowers used a higher order Fourier analysis and introduced his famous Gowers norm, which controls the randomness of the set in the question. For me the absolutely striking result was the fundamental theorem of Ben Green and Terence Tao which states that among the primes there are arbitrarily long arithmetic progressions.

Timothy Gowers (left) and Endre Szemerédi (right)

They and other mathematicians are those who really moved this field. Without them my theorem would be just a good theorem and nothing more. They strengthened it, invented many revolutionary new ideas, found connections, between different branches of mathematics and getting unbelievable results. They are doing unbelievable things.

My original proof contains a graph theoretical lemma called a week regularity lemma. The regularity lemma was needed for something else, namely for a graph theoretical problem. I listened to a lecture by Béla Bollobás, which was in 1974 in Calgary. He talked about the Erdős–Stone theorem. Bollobás and Erdős wanted to determine the right magnitude, and they had a very good bound, the order was log n and only the constant was missing a little bit. I decided to work on it, as I liked the problem and Béla presents things very nicely and extremely cleverly. Then I realized that maybe a lemma like the regularity lemma would help considerably. Actually, that was the real reason why the regularity lemma was invented. At least, this is my recollection. I would like to thank Vasek Chvatal for helping me to write up the regularity lemma. Later we together found the exact constant for the Erdős–Stone theorem. Although the regularity lemma was created for a particular problem, it later found many important applications. In discrete mathematics and theoretical computer science. Gowers, Rodle, Nagle, Skokan, Schacht found hypergraph regularity lemmas and a hypergraph removal lemma. These lemmas are extremely powerful and they have a wide range of application in arithmetic combinatorics and computer science.

I would like to mention briefly some other results.

• 1. My favorite work is the creation of the pseudo-random method together with Miklós Ajtai and János Komlós (it may be that the pseudo-random method existed in some other areas of mathematics). We used this method, when we tried to give a better estimate on density of an infinite Sidon sequence. Using this method, we also disproved Heilbronn’s conjecture, which was at that time already 40 years old.

• 2. Euclid’s system of axioms state some of the basic facts about incidences between points and lines in the plane. In the 1940s, Paul Erdős started asking slightly more complicated questions about incidences that even Euclid would have understood. An interesting question is that at most how many incidences can occur among n points and n lines, where an incidence means that a line passes trough a point. My theorem with Trotter confirmed Erdős’s rather surprising conjecture: The maximum number of incidences is much smaller in the real plane than in the projective one—much smaller than what we could deduce by simple combinatorial considerations.

• 3. Together with Paul Erdős, we discovered an interesting phenomenon and made the first nontrivial step in exploring it. We noticed, roughly speaking, that a set of numbers may have nice additive properties or nice multiplicative properties, but not both at the same time. This has meanwhile been generalized to finite fields and other structures by Bourgain, Katz, Tao, and others. Their results had far-reaching consequences in seemingly unrelated fields of mathematics.

• 4. We want to sort n numbers, that is to put them in increasing order by using comparisons of pairs of elements. Our algorithm is non-adaptive. The next comparison never depends on the outcome of the previous one. Moreover the algorithm can efficiently run simultaneously on cn processors such that every number is processed by only one of them at a time. Somewhat surprisingly our algorithm does not require more comparisons than any adaptive nonparallel-shorting algorithm.

After returning from Moscow I continued to work at the Rényi Alfréd Mathematical Institute. From time to time, either with the family or alone, I visited different universities, mainly in the US. Ron Graham suggested to Donald Knuth to invite me to Stanford University. There I started to work on theoretical computer science too. Donald Knuth and László Babai encouraged me to continue to work on that discipline. I thank them for this.

With the family we spent two years at the University of South Carolina, in Columbia. I am very thankful to Tom Trotter who, when I became seriously ill, helped enormously.

In 1990 I got a tenured position at Rutgers University. I am still a member of the Department of the Computer Science. I enjoy teaching both, undergraduate and graduate levels also supervising PhD students.

Being 72, I am a professor emeritus at the Rényi Institute. My plan is to start to study analytical number theory, although I am well aware that most probably I will never get any significant result. I am still working on my old problems.

I would like to say some words about the Abel Prize. As I said in my acceptance speech, I consider this award a recognition of discrete mathematics and theoretical computer science. Also this award could not have happened were it not for the fundamental work of many mathematicians who might have been influenced by some of my results and methods, but who have developed much stronger results and established deep connections between different branches of mathematics.

I live with my wife Anna. Our five children, Andrea, Anita, Peter, Kati, Zsuzsi and five grandchildren, Krisztian, Tibi, Szandi, Matyi and Liza live in Budapest, London and Madrid. Nevertheless we see each other very often.

The Szemerédi family