In Our Time - Paul Erdős

Episode Date: March 23, 2023

Paul Erdős (1913 – 1996) is one of the most celebrated mathematicians of the 20th century. During his long career, he made a number of impressive advances in our understanding of maths and developed whole new fields in the subject. He was born into a Jewish family in Hungary just before the outbreak of World War I, and his life was shaped by the rise of fascism in Europe, anti-Semitism and the Cold War. His reputation for mathematical problem solving is unrivalled and he was extraordinarily prolific. He produced more than 1,500 papers and collaborated with around 500 other academics. He also had an unconventional lifestyle. Instead of having a long-term post at one university, he spent much of his life travelling around visiting other mathematicians, often staying for just a few days. With Colva Roney-Dougal Professor of Pure Mathematics at the University of St AndrewsTimothy Gowers Professor of Mathematics at the College de France in Paris and Fellow of Trinity College, CambridgeandAndrew Treglown Associate Professor in Mathematics at the University of BirminghamThe image above shows a graph occurring in Ramsey Theory. It was created by Dr Katherine Staden, lecturer in the School of Mathematics at the Open University.

BBC Sounds, music, radio, podcasts. Thanks for downloading this episode of In Our Time. There's a reading list to go with it on our website, and you can get news about our programs if you follow us on Twitter at BBC In Our Time. I hope you enjoyed the program. Hello, Paul Ayrdush, 1913 to 1996, it's one of the most celebrated mathematicians of the 20th century. During his long career, he made a number of impressive advances in our understanding of maths

and developed whole new fields in the science. subject. Born into a Jewish family in Hungary, just before the outbreak of World War I, his life was shaped by the rise of fascism in Europe, anti-Semitism and the Cold War. His reputation of mathematical problem solving is unrivaled, and is extraordinary prolific. He produced more than 1,500 papers and collaborated with around 500 other academics. He also had an unconventional lifestyle. Instead of having a long-term post at one university, he spent much of his life traveling around. visiting other mathematicians

often staying for just a few days. With me to discuss the career of Paul Erdush are Timothy Goers, Professor of Mathematics at the College of France in Paris and Philip Trinity College, Cambridge. Andrew Tleghan, Associate Professor in Mathematics at the University of Birmingham, and Colver Rodi Doogle,

Professor of Pure Mathematics at the University of St Andrews. Colver, would you start by telling something about his early childhood? Sure. He was born to a middle-class family in Budapest and in... March of 1913. Both of his parents were high school teachers. They both taught maths and physics, his mother and his father, and on some level he should have been set for a pretty comfortable existence. There were two particularly notable aspects of his early childhood, though. So the first was

that when she went in to hospital to give birth to him, his mother already had two girls. He had two older sisters, and a wave of scarlet fever went through Budapest while she was in hospital. And as he was being born, both of what would have been his elder sisters died. So this was a deeply traumatic event for the whole family, as you can imagine, and meant that his parents were very, very protective of him for all of his childhood after that. By his own admission, he didn't butter his own bread until he first arrived at Trinity College at the age of 21. And then the second really significant event that happened early in his life was World War I broke out, and his father went off to fight in the war and was captured by the Soviets almost immediately and didn't return.

for seven years. So he was in a very, very intense relationship just with his mother from an early age. Then we had an extreme right-wing government came to power in Hungary, and then what? What happened to him? So his mother had briefly been promoted to head mistress by the communist government just before the extremely right-wing one, and as a consequence of that, she lost her job as a teacher when they came into power. She still managed to make a living. She was tutoring him, but that meant she was having to work quite hard going to different tutoring classes and he was left mostly in the care of a governess while she was out working. He said he taught himself to count at the age of three

by trying to count down the days until he could see his mother for the daytimes again. And then as he went through his childhood, various anti-Semitic laws were passed, of which probably the most pertinent to him was one called Numerous Klausus, which restricted the number of Jewish students at universities to 6%. which was roughly the proportion of the population that was Jewish at the time, but was much, much less than what had been the proportion of Jews going to university. So it was clear from a very early age that it was going to be hard for him to have an academic career in Hungary. There are these stories of his prodigious intelligence at the age of three, at the age of five,

I mean, somebody would say, give me a number, and the man would say, four, five, six, seven, eight, and he would cube it or... How would you make of that? Is that taught or is that inherited? Did this idea, it's a clear as I've come across, of some genius just popping up, or did it just pop up? How does that happen? I think it must have just popped up in him.

That kind of facility with early calculation seems to be randomly distributed around people. It's rare. It doesn't necessarily correlate with being good at maths later on, but in his case, it most squarely did. He said that because he was left alone by his parents so much, he just became obsessed with numbers as a way of passing the time. Andrew, how did he begin to share, well, we've edged in terms. to that, but how did he begin to show his mathematical talent so that others besides his mother saw it?

When his mum's friends came round, he would ask them, how old are you? And he would then tell them how many seconds they'd live for. But then really, I guess the big breakthrough was when he was a teenager. So in Hungary, they have this lovely culture of journals, so journals for high school children. And in them, you'll have mathematical problems stated each month. Then students would write in, and give what they thought was the solution. And then in the next month, the winners, the people that were correct, they would be announced. So at that stage, Airdush was one of the most prolific problem solvers

in these high school journals, along with some other actually very good mathematicians. It turned out people like Paul Turan as well. So he sort of made a name for himself as a problem solver, even in his teenage years. He took a first class degree and his PhD at the same time, when he was about 17. Yeah, so he went to university, the University of Budapest.

age 17. As you said, he was doing them both simultaneously, and even at an early stage, he was doing novel research. So he was often meeting other young mathematicians, people like Paul Turan, George Sekares. They were meeting in parks or they're going for walks, and they were talking about mathematics, bouncing off each other, getting ideas from each other. It was also a very significant point in his life, not just in the sort of circle around Budapest, but also he made a name for himself in the number theory community. So he really, when it was a, um, So he, well, just a couple of years after that, but still during his undergraduate. So he reproved something called Chebichev's theorem,

and Chebichov's theorem was around since the 19th century, but he gave a very elegant and simple and clever proof of this. Thank you very much. Tim, can we have a little more detail about this theorem, Chebyshev's theorem, and the difference between the old proof and the new proof that Dosh came up with? Chebyshev's theorem concerns prime numbers. Those are numbers like 2, 3, 5, 7, 11, which don't have any factors apart from the obvious ones, 1 and themselves. So, for example, 9 is not a prime number because it's 3 times 3, but 11, you can only write it as 1 times 11, and so that is a prime number. If you start asking yourself questions like, can you write a formula for the nth largest prime number?

It seems to be remarkably difficult. In fact, it's generally believed now that there is no usable, sensible formula for the nth number. largest prime number. And just being some number. So it's an arbitrary number. So a formula that would tell you for any given integer like a million or a billion, what the millionth largest number is or the billionth largest number. It's not believed that such a formula exists. So instead, what we try to do is look a little bit, it'll stand back a little bit and just ask ourselves questions like roughly how many primes are there between one and any given number that you specify. Can you have a formula that just at least approximates the number of primes.

And Chebyshef, what he did was solve a problem known as Bertrand's postulate, which had been posed five years earlier, which says that between any number and twice that number, there must be a prime. Euclid had already proved millennia earlier that there are infinitely many primes. So this is a much more precise result. It says between any number and twice that number, there must be a prime, which in particular implies that there must be infinitely many primes. But Chebyshev's method was in some ways quite advanced.

You need quite a lot of mathematical expertise to read it. Airdush came up with a new proof of Chebyshev's theorem, which I've read some, it's described as something that if you've got a maths A-level, you can understand this proof. There's a word that mathematicians use, which is the word elementary. And elementary doesn't mean easy, but it means it's built out of easy ingredients. So if you've got the ingredients, if you've got the knowledge of an A-level student and a bit of patience and willingness to try to understand this proof,

then you can, whereas if you try to understand Chebyshev's proof, you have to have learnt quite a lot more mathematics. Actually, you get a little bit more out of Chebyshev's argument. You don't just get that there's a prime between N and 2N, but you also get a reasonable estimate for how many primes there are up to any given number. When I say reasonable, what I mean is you can say that it's at least this number and at most twice that number, something like that.

So it narrows it down to within a fact. of two, as we would say. Do you mathematicians do this for the joy of it, like people sing, or do you because it has some end use? I would say both, so we do it for the joy of it, but we're very fortunate in that quite a lot of what we do does eventually turn out to have an end use, and so for that reason, people are prepared to, so to speak, subsidise our hobby. Can you give us an end use?

This is almost a cliched example. Not quite cliches, I'm welcome. But number theory of which this is an example and factorisation and prime numbers and things are absolutely essential to the method of cryptography that we use in order to be able to do transactions, financial transactions safely online. So that's a very big application of mathematics.

But there are many, many others. Thank you. Colbert. So he's been to university, he's a starter, and he's going to do mathematics for the rest of his life. And then you came across to Manchester University for four or five years. What was that all about? So he'd been invited by a number theorist called Mordell

to go and work with the group in Manchester. His fame had become quite great by this point. Isaiah Shure, who's a wonderful number theorist, had christened him, the wizard from Budapest for his skill. So it hadn't been so hard for him to find a job. Since he was young, his parents had known that he would have to leave Hungary. So the state of attacks on the Jewish population and there was such that it was clear he could never be an academic in Hungary.

His mother had suggested that maybe they should convert when he was seven. And he had turned to her and said, You may do what you like, but I shall stay as I was born, which is a statement from a seven-year-old is quite remarkable. So they had made sure that he could speak English and French and German as well as Hungarian, and he packed his bags and went off via Vienna and briefly stopping in Trinity College, Cambridge, and on to Manchester. Who did he work within Manchester that was in?

important to him and to them? So Mordell was his boss in Manchester. He did a lot of work with Hardy and Littlewood in Cambridge when he was there. And he also started working on what became known later as the Erdush Khorado theorem, but for strange reasons wasn't published until the 1960s. So he started really cooking up this blend of number theory and combinatorics that was to stay with him for the rest of his life while he was in Manchester. But it wasn't that he only collaborated with people in Manchester. He started working with everybody he could. Was this unusual? Yes, I would say so. So most... The collaboration I mean, yes, absolutely. So most people at the time mostly worked on their own, whereas Erdisch from a very early age, possibly started by the walks that Andrews already mentioned around

Budapest, with his friends as an undergraduate, loved to do maths with other people. He did do maths on his own, but he strongly preferred to work with others. And he would go to Cambridge often for the weekend. He was travelling all around Britain working with people. And at the end of three years, it was becoming increasingly clear that Hitler was getting more and more dangerous and that he decided he needed to leave Europe for good. So after a final visit back to Budapest in the summer of 1938,

he charged back to London, got on the Queen Mary and set sail for the Institute for Advanced Studies in Princeton. And did you get anything else out of the Manchester experience? That was when he first started getting interested in lots of questions, about what do numbers look like on average? So Tim's already given us the definition of a prime number, which is a number that's only divisible by one in itself. He got interested in the question of how many different prime numbers divide a given number. So say, for example, 12 is only divisible by two. Eight is only divisible by two. That's the only prime that divides into eight.

So that's got a score of one, whereas if I go for 30, because that's two times three times five, that's got a score of three. And so he got very interested in the question of not just is a number a prime and can I count the primes, but can I count how many divisors there are of a given number? And he proved his first results in that direction while he was in Manchester. And it was because of that and similar results that he was eventually able to get the fellowship at the Institute for Advanced Studies, which I should mention the pull factor as well as the push factors. It was described as an intellectual paradise, the Institute for Advanced Studies. In America? Yes, in America. So it was only five years old. Einstein was its first professor.

there were zero students, no teaching responsibilities, one could just go there and do mathematics and theoretical physics to one's heart's content. And John von Neumann, who's famous for many things, including work on the nuclear bomb and game theory and economics, managed to get a fellowship for Erdos to go at work there. And that financed him, did it? That financed him for the first year.

At the end of that first year, for reasons that are unclear, he applied for a renewal and wasn't granted it. And Einstein argued strongly for him to get a further job and said he had used strong words the like of which he had not used before to try and enable Erdish to stay, but somehow he was deemed not the right fit and there were so many Jewish mathematicians coming over.

You're many clues to why I wasn't the right fit? I mean, he seems to do mathematics all the time with mathematicians and so what was he doing that upset people? I think he was maybe a bit wild in some of his behaviour. I mean, I never met him. I'm just a bit too young to have done so. There's a quote saying that Princeton didn't want to keep him because he was uncouth and unconventional.

So he was definitely unconventional in a sense that he would speak his mind freely. There's stories about when he's talking with people, I mean this is a few years later, but talking with people to do with the Manhattan Project in a restaurant he loudly says, oh, how's the A-bomb going? So he's very uncouth in that sense.

It's a big thing for a man that intelligent backed by a person like Einstein to be kicked out, isn't it? Or am I? Yeah, of course it is. Yeah. So is there any more reasons? I did meet him. actually, but he was pretty old and I was quite young. And by that time, I think he had sort of morphed into a sort of eccentric old man, not somebody that one would, who would rub anybody up the wrong way. It is worth mentioning that the, I mean, this is now 1939 and the number of

Jewish scientists and mathematicians are attempting to get out of Europe and into America is very, very high. And that's part of the reason why there's such competition for posts. Can you tell us, give us some idea then when he gets to America, what does he start to work on? I think he's working on a range of things at that stage. So he's interested in something called discrete mathematics. What's no? So discrete mathematics is the study of discrete mathematical objects. So what's a discrete mathematical object?

It's an object that in some sense is non-continuous or countable in some sense. So if you look at the whole numbers, a whole numbers, one, two, three, four and so on, that is countable. You can list the numbers as an ordering of those numbers. It's also non-continuous in a sense that but there's a gap between one and two. There's a gap there. It's not a continuous thing. So there's a gap between one and two, two and three and so on. So he starts getting interested in discrete mathematics. And this is a topic which is perhaps a bit unfashionable at the time. He starts getting interesting in things called graph theory, so the study of networks. He's interested in Ramsey theory, which is the study of complete disorder as impossible. So he was so driven by mathematics and curious about different aspects of mathematics that he was willing to go out there and well, problems that maybe weren't as fashionable to other mathematicians.

But America suited him, and yet he had to leave it. So I guess you're now talking about the 1950s, yeah. So it's kind of a bit unfortunate. So he had a temporary position at the University of Notre Dame, as the Americans call it. He actually was offered a permanent position there, but he turned it down. He suited the nomadic lifestyle. At some stage, he wanted to go to Amsterdam, to a conference, and they refused him entry back into the US again.

Partly it's just because of the time it was. It was the McCarthy era of the 1950s where America was just suspicious of foreigners, particularly from communist countries. Also, there was an FBI file on him. He was walking in Long Island with some other mathematicians and they didn't see the no trespassing sign and they were talking about maths wandered through to this military transmitter

and then they were sort of nabbed by the FBI and it was all cleared up, but it created an FBI file on him I think it was just an excuse to get rid of him. So graph theory has been mentioned, Tim. Can you take it in that direction? Certainly. The first thing to say is that there's an unfortunate terminological clash, which is that the word graph,

as used by most people, means something you plot that shows how one thing depends on another. It might be COVID cases as a function of time or something like that. But we're talking here about, when you talk about graph theory, it's a completely different meaning, and a better word, but unfortunately not the word that most people use, is a word that Andrew just mentioned, it's the word network.

So you can think of a graph as a bunch of points, which if you're using the language of networks, you might call nodes. And some of the points are joined together by lines, which are known as edges. And that's all there is to a graph, a bunch of points, some joined by edges. So you might ask, why is that important? And the reason is that it can be, or one reason, is that graphs can be used to model a huge number of phenomena because the points, which we call vertices,

can represent objects of a certain kind, and the lines joining them, the edges, can represent potential relationships between them. So to give a few examples, points could represent websites, and you could join two points by an edge if there's a link between those two websites, and then you get a graph that is somehow modeling,

in a certain sense, the structure of the internet. Or points could represent people, and you could join two points by an edge if those two people are friends with each other, and you get a sort of social network modelled by a graph there. And then you also have graphs in pure mathematics. For example, if you just take a shape like a cube

and you look at it, it's got some points. It's got the vertices of the cube, and some of those vertices are joined by edges. So a cube is a graph, or can be thought of as a graph, with eight vertices and 12 edges. So graphs have both an importance for modelling real-life phenomena,

which it often turns out that you can get a lot of insights, into the real world phenomena by forgetting all the details except this underlying graph and also they model various purely mathematical phenomena. He was a problem solver, wasn't he basically? Erdash was, yes.

That was what he's maybe mostly remembered for. It's just a supreme, not just problem solver but also problem poser. He asked a lot of questions and the ones that he particularly liked, he would offer monetary rewards for which varied from something like, you know, $30

all the way up to several thousand dollars depending on how important or difficult he thought the problem was. He gave money to so many good causes. He gave away all the money he got, basically. And he didn't have much of that. He won the Wolf Prize and then just gave it basically. He kept a little bit as he needed to get from his next person who was spending the night with and gave all the rest away.

Yeah, it was $50,000 and he said he kept 720. Colver, one of the fields of maths that he developed extensive was Ramsey Theory. So where you go? So, Ramsey theory starts with a particular problem, which I'm very fond of, called the party problem. And I'll give the first interesting instance of it as an example now. It says, how many guests do you need to have at a party to guarantee that either at least three of them all know each other or at least three of them all don't know each other? So how big a party do I have to have if I definitely want three friends that can stand in the corner and catch up on gossip or to find three people who've not met before who can be.

introduced to each other. So I'm going to show you how to see that six people is enough. So imagine that I'm hosting a party and I've invited five friends. But maybe they're not my friends. We're interested in maybe them knowing each other or not knowing each other. So these five people, they might know me or not know me. So there's two possibilities and there's five of them. So at least three of them must fall into one of the cases. It's not possible for two of them to not know me and two of them to know me. The fifth person has to go somewhere. So let's assume that three of them know me. I'll talk about the other case afterwards. And think about those three people. So maybe the three of you, I guess at my party and then you all know me, then maybe two of you know each other.

And then the two of you plus me make three people that all know each other. And if that's not the case, then no two of you know each other. And so the three of you form three people that don't know each other. And so we managed to do that with six people. If I'd said that at least three people didn't know me, we would have swapped everything round. That's the first question of Ramsey theory. And that shows that six people is enough if I want three to know each other or not. So I can replace that three by any other number. I can say I want a party that's big enough for 17 people to all know each other or 17 to not. And Frank Ramsey had proved that there always is a big enough party,

no matter how many people there's always a big enough party. Now, Erdisch came along and firstly found a much nicer, simpler, better way of proving that there's always a big enough party. And his banged on how many people you need at the party was smaller than the previously known band. He also was able to show a lower band on how many people. So a party size which is definitely not big enough using some beautiful arguments and essentially took what had been this single loan result and turned it into an entire theory of mathematics, which people spend their whole careers working on nowadays. Andrew, you want to come in. Yeah. So one thing I wanted to say

as well is that Ramsey theory isn't just about graphs and about these parties, but actually this phenomenon occurs elsewhere in mathematics. So Tim talked about one of Erdisch's, about his open problem. So one of his most famous open problems is the happy ending problem. And this is a problem in Ramsey theory. Here, you, rather than looking at a party, you've got a collection of points that you draw on a piece of paper. So imagine you draw three points on a piece of paper. And as long as they're not in a straight line, well, those three points will be the corners of a triangle. Now, what about if I give you four points? Well, those four points may not form a four-sided shape, because you can draw a triangle and then you can plop another point in the middle,

and that's not a four-sided shape. It's not the corners of a four-sided shape, what we call a convex quadrilateral. Actually, you can ask this question more generally. How many points do you need to put on a piece of paper, such that some of those points form your favourite, I don't know, pentagon, your six-sided shape, the seven-sided shape, and so on. What Airdish and George Seckeres showed is actually these,

there's always a solution to this problem. In a similar way to the party problem, there is a solution. If you put enough points on a piece of paper, you're going to get your n-sided shape somewhere in that picture. So this was worked on 80 years ago by Edison-Secraez. They actually just asked the question of what's the right answer? How small? How many points do you need to put on a piece of paper,

such that as long as no three of them are in a line, then somewhere in that, end points will form the corners of an n-sided shape. And we don't know the answer even now. We don't know the exact answer. We know there is some answer, but we don't know exactly what it is. Do you think you ever will?

Oh, that's a tough one. Because actually, very few problems in Ramsey theory do we think that we're going to get an exact solution to? This is one where we actually have a reasonably good, it's what we call an asymptotic solution. So as N is large, if we're looking at an n-sided shape where N is large, we have a reasonably good answer to it. But I think probably the answer is probably not exactly. Can we go to continue this, Tim, with you? We come up with the phrase the probabilistic method. What's that about and what's its significance?

Well, I think the easiest way to illustrate that is to go back to what Colba was saying about the party problem and the question you can ask, how many people do you need in order to guarantee that some fixed number, be it 17 or 100 or whatever, either all know each other or all don't know each other. If you want to show that you need a lot of people, then you've got to come up with some sort of configuration of, or some sort of knowledge network, so to speak, or equivalently some graph, that demonstrates that you really do need a lot of people. And the difficulty with the problem is that if you sit down and try to design this person knows that person or this person doesn't know that person and so on,

it's incredibly difficult to write down a specification that demonstrates that you really do need anything like as many people as the proof requires. And it genuinely is very, very difficult to design this. Eredge had a brilliant idea which was, if it's difficult to design it, don't design it. What do you do instead? well it's called the probabilistic method what you do instead is you just choose your network entirely at random

so for each pair of people you toss a coin if it's heads they know each other if it's tails they don't know each other and it turns out that if you do that then you can show that it's extremely likely that you're going to need an absolutely huge number of people before you get your specified number

that either all know each other or all don't know each other this is very counterintuitive because you might think that if almost everything works, then surely you can just sit down and write down something that will work. But unfortunately, the set of things that you can actually describe is a very small set. And so you can't sort of rule out that all the ones you can describe happen to be the unfortunate ones that don't work.

So you know that almost everything works. And this phenomenon actually occurs. So what makes it particularly important is that it occurred in this one example. But once you've seen this example, it just changes the way you think as a mathematician. And then you start seeing this phenomenon all over the place. There are many, many situations where it's very hard to describe a mathematical object that explicitly that has certain properties, but much easier just to show that almost every object has those properties.

It's a very strange phenomenon, but it's a very important one. And where does that lead you? For eardush, it led to a lot of other solutions to problems in graph theory and other areas where they had seemed extremely hard, but once you have this idea that perhaps you could just try choosing a random object and seeing if that almost always works, they become suddenly much easier. Picking up the word random, Colva,

random graph theory, Erdash was into that. What did he find that? What did you do with it? So in a series of eight papers with Alfred Rennie, who's another Hungarian mathematician, Erdoshen Rennie invented the field of random graph theory from scratch and proved that it was important. So the model that they were imagining,

they had two different ones, but I'll talk about one in particular, is that you pick some number of vertices and you pick a probability, so maybe your probability is a half. And you look at all the possible pairs of vertices and you put in each edge randomly with probability a half. And you ask yourself, what can I say about the resulting graph? Is it possible, for example, for me to walk along the edges from one vertex to any other

or is it going to break into different bits? Am I going to be able to colour the vertices with some number of colours such that no two vertices sharing and edge are the same colour. And this model of random graphs, they proved amazingly precise properties about it, which I think Tim will tell us more about in a minute. But it's turned out to be incredibly important for lots and lots of real world applications. So, for example, during the COVID pandemic, one of the models that was used when trying to analyse

if household bubbling could change over Christmas, if one remembers that dark Christmas, was modelling our interactions with each other as a random graph. we're all in households between one and about four people, and then somewhat randomly we know people in other households. And so if somebody in one household gets infected, probably everybody in that household gets infected. But if they randomly meet with other people,

the infection might or might not spread along the edges in our graph of knowing and not knowing. And that really does help to feed into questions about whether or not we could meet each other. Do you want to develop that, Tim? Well, just to say that, I suppose it gives another very good example of an application of graph theory. It's another network. So the vertices

there would be people and the edges would be something like you've joined two people by an edge if they come into close proximity. And sometimes you can do something a little bit more. You can attach a weight to an edge. So you could say that maybe if two people meet all the time because

they live in the same house, you attach a high weight which means it's more likely that the disease will transmit. Whereas if they just happen to meet each other in a shop while they're buying bread or something, then there'll be that would be an edge, but with much lower weight. So this weighted graph is fundamental to the whole sort of area of epidemiology. You can get a lot of insight into how a disease spreads just from the graph theory.

Andrew, he liked to question himself, didn't he, pose a problem for himself to solve, as well as finding problems that had not been fully solved to his satisfaction. Yes, so his mantra was to prove and conjecture. So by conjecture we mean pose open problems. and it wasn't just for himself that he would pose problems. What he saw was that it was a duty of a mathematician to sort of lay the marker points for other mathematicians to follow and say, this is an interesting question.

And as Tim mentioned earlier, he would often assign money to these problems just to act as a guy, the more the problem was worth, the more interested he was in the problem being solved. So actually many of his problems have been solved since he died. one example of this is so we mentioned prime numbers earlier so one special case of one of his

conjectures is that in prime numbers in the set of prime numbers we know there's infinitely many but inside them there are arithmetic progressions of arbitrary length so what do I mean by that I mean if you take an arithmetic progression is you start with some number and then you have a series of numbers whose differences are the same something like two five eight eleven fourteen they all differ

by three there. So that was, for example, a special case of one of Edish's problems that was solved about 18, 19 years ago by Green and Tao. So if you've got the set of prime numbers, then there's always going to be an arbitrary long arithmetic progression.

So you can go on forever finding this arithmetic progression. And that's quite counterintuitive, actually, because as was mentioned earlier, primes are kind of sparse. There's infinite many, but they get less and less frequent, or the density of them inside the whole numbers is less and less frequent. And to have this regular structure,

Airdris was just great at posing problems. And I think sometimes he was willing just to take a punt and he would pose a question that was just interesting to him. And sometimes they would pay off and they would leave to fruitful research directions and sometimes they weren't necessarily paying off. But the point was he was so willing to go out there and pose problems that it's led to new directions emerging in mathematics.

Here's another phrase I only encountered the other day. Tim, that's the threshold phenomenon. That's a fascinating phenomenon that he observed in his work with Alfred Reni. Caldva mentioned the property of a graph. It's called a graph connected if you can get from any vertex in the graph to any other vertex by going along a path down some of its edges. They showed that if you start with no edges at all, and then you just randomly put in an edge and randomly put in another edge

and randomly put in another edge, and you just keep on going like that. And for a long time, the chances that the graph is connected, it's almost certain that it won't be connected. Then you get to a certain point, the threshold, and just beyond the threshold, it suddenly jumps from almost certainly not being connected to almost certainly being connected.

The point at which you go from almost certainly not being connected to almost certainly being connected just jumps extremely fast, and this is called the threshold phenomenon. Do you know why that happens? Well, I do, but it's a sort of complicated mathematical proof. I think the main thing to say is that this phenomenon turns out to be extremely widespread. And it also occurs in physics. In statistical physics, it would be known as a phase transition.

The graph just suddenly goes from having one phase where it's not connected to another phase where it is connected. There are also many open problems concerning phase transitions. When you get a little bit more complicated than the properties that are the same. and Rainey studied for graphs, you can get problems that are very interesting and important. Important for what? For example, there's a phenomenon called a self-avoiding walk. That's a random walk amongst points that never visits itself twice. And that can model something like a long piece of DNA

that can't occupy the same point more than once, understanding various structures that occur in chemistry and things like that. So understanding phase transitions is very important. it's an interesting area where physicists would say that they understand a lot more than mathematicians do because mathematicians are looking for completely rigorous proofs of these phenomena, whereas physicists are sort of satisfied with slightly more heuristic arguments, let's say. Do we need to say more about randomness in relation to number theory? Absolutely. So one of the many fields which Erdisch founded,

and the one that he described himself as being proudest of, is known as probabilistic number theory. Now number theory is a number theory is a number. about properties of the whole numbers, and the bit of it he was most interested in is this question of divisibility by primes that's come up a few times before now. And it doesn't seem like randomness should have anything to do with it.

I mean, the fact that 12 is 2 times, 2 times 3 is not random. That's set in stone. But together with a Polish mathematician, Mark Katch, they worked out that if, rather than looking at individual numbers and asking how many different primes divide a number, they started looking at large sets of numbers, say all the numbers up to a million, or all the numbers up to a million, million,

and asked how many primes divided all of them and looked at the count, and drew a graph of it, say, not graph in the sense of vertices and edges, but graph in the sense of like a bar chart, say, the resulting chart winds up looking just like the bell curve histogram that we see across all sorts of real-world things. So were you to toss a coin a thousand times and record the number of heads and tails and then do it again and do it again and do it again and record how many heads you've got. On average, you'd expect to get about 500 heads,

but you wouldn't get perfectly 500 heads every time you'd get mostly 500, some 499, some 501, some slightly fewer 502 and so on. And it would come down in that lovely bell-shaped curve that I'm sure lots of our listeners have seen in many contexts. He discovered that we get a curve like that when we ask about the number of prime devisers. And it's kind of incredible. put my little laptop to work coming down yesterday on the train and asked it to do this count for me for all the numbers up to a million. And his formula predicts that the average number of prime divisors should be between two and three, a bit closer to three than two. Now, you can't have

two and a half prime devices, of course. So what my computer returned to me was that the most common answer was three, and then shortly after that was two, and then shortly after that was four, and then there's a few primes and powers of primes, and then five and six and seven were the smallest numbers, there's only seven numbers less than a million that are divisible by seven primes. So even at a million, I could see this kind of bell curve phenomena beginning. And nobody had thought of mixing probability and divisibility by primes like that before. And once you've got the idea of doing that, you can ask all sorts of other questions too. Jim, he's seen as more of a problem solver than a theory developer. Do you agree with that?

I do. It's a distinction which is more a matter of emphasis than as a little. absolute distinction because if you look at the problems that he posed, once you start thinking about it, and it may just look like a whole lot of isolated problems, but once you actually start thinking about them, you realise that there are difficulties, sort of quite deep difficulties associated with the problems, and that in order to solve the problems, you're forced to come up with ideas. You suddenly get a sense that Erdush, these problems hadn't come out of nowhere, they'd come out of some quite deep thought. Nevertheless, it is the case that there is a contrast between the way different mathematicians operate.

And some would say that what they're really trying to do is improve their understanding. And if they improve their understanding, then solving problems will be a consequence of that. And others, and Erdus, more like the other kind, would say that what they really want to do is solve problems. By solving problems, they will improve understanding. And it was a very nice metaphor of the mathematician Alexander Grotendig, who said that he considered the idea of a nut. you want to open a nut, two approaches. One is you get a nut cracker and you squeeze as hard as you can

until the nut breaks and then you've got inside. Grotendik's preferred approach was to put the nut into some sort of liquid and just leave it there for a very, very long time until the shell softened and it opened very easily. So Grotendik regarded himself as more of a theory builder, somebody who wants his understanding to improve until problems get solved easily. And I think Erdush was more of the other kind. where he just wanted to go straight in and directly attack problems.

Yeah, he had a lovely discussion of the problems he posed himself, and he said some of them were like marshmallows, in that they were incredibly tasty to solve, but dissolve on your mouth quite quickly afterwards and leave not much left, whereas others were like acorns, in that trying to solve them could produce the roots of a huge mathematical tree. So I think he himself was aware of these different ways problem solving could go. Andrew, can you start getting towards the end now?

What's an Erdosh number? Yeah, so an erdisch number is a bit of mathematical fun, really. We like to measure our distance as mathematicians from Erdisch. So if you are poor Erdish, you have an Erdisch number of zero. If you've written a paper with Paul Erdisch, you have an Erdish number of 1. If you've written a paper with someone that's written a paper with Erdisch, you have an Erdish number of 2 and so on and so forth. So to put in some context, because Erdish had about 500 co-authors, there's about 500 people with an Erdish number of 1. already there's more than 10,000 people with an Airdish number of 2

and it's not just mathematicians so Albert Einstein has an Airdish number of 2 for example So most mathematicians have an HEDA number somewhere between 1 and 5 And actually, you know, it's not that impressive to have a small Airdish number I'd be more impressed with finding someone with an Airdish number of 10 a mathematician because I'd wonder how did they get that far removed from Aerdish's work So each of you, what's your Airdis number and what does it mean? Starting with you, Colver Well, my PhD supervisor, Peter Cameron, collaborated with Erdush,

and I have since published with my PhD supervisor, so my Erdush number is two. Likewise, I have an Erdisch number of two, so I worked with a mathematician called Sasser Kastoska, who happened to work with Erdish, so that's my Erdush number as well. And mine should be two, because my supervisor was a close collaborator of Erdush, but actually I've never had a joint paper with my supervisor, so for a long time it was four, and then a few years ago it went down to three. I collaborated with someone who collaborated with someone who collaborated with Eredash. It's a crass question to ask him.

Just as much of the interest, how do you rate him? I think the biggest compliment I can make as a discrete mathematician as a commonatorialist, is that it's very hard to work on a problem and not be influenced by Airdush. So what I'll do when I'm approaching a problem is I'll try and do things randomly. I'll do the probabilistic method. Or I think, oh, is there some Ramsey-type behaviour here? So as someone working in his field, I think on a weekly, on a monthly basis, I'm influenced by him. So in that sense, he was incredibly important.

Yeah, I would say the same. I also work in very much sort of Erdush style mathematics. You can't escape his influence, nor would you want to, because he had such amazing ideas. I'd like to, yeah, I mean, echo the previous two remarks, but also to say quite apart from his mathematical influence, I think this collaborative style of doing mathematics really has changed maths for the good. most of my research is in collaboration with other people. It's made being a mathematician a completely different thing from what it might have been before him.

And it might have tended that way anyway, but his fondness for collaboration, his support of lots of female mathematicians who he worked with, and his insistence on beauty in mathematics and finding joy in mathematics have really changed it for all of us. There was a lovely limerick about him, which I'd love to tell, which he was delighted by.

So a conjecture both deep and profound Asserts that a circle is round In a paper by Erdisch Written in Kurdish, a counter-example is found And Erdisch was so pleased by this He tried to publish a paper in Kurdish But unfortunately couldn't find a journal to do so But that sense of playfulness and joy in what we do

is a wonderful thing to have left the rest of us Well, that was terrific, thank you very much And I'll have to listen to it several times but still. Thank you very much. Thanks, Colver. Rony Dougal, Andrew Treglone and Timothy Gowers. And our studio engineer, Jackie Marjoram, next week, Megaliths, the stone monuments first built in Britain around 6,000 years ago. Thank you for listening. And the In Our Time podcast gets some extra time now with a few minutes of bonus material from Melvin and his guests. What would you like to have said that you didn't have time to say?

One thing we didn't mention was this notion of a proof from the book. so Erdush being this sort of eccentric cheeky chap that he was, he was an atheist, he didn't believe in God, but he says you don't have to believe in God, but you should believe in the book. So what did he mean by this? So he has this idea that next to God there's this book, and inside this book are the proofs of every theorem in mathematics.

But it's not just any old proof, it's the most beautiful and elegant proof that there is for that particular theorem. And that was a very strong idea in his work, you know, if he saw one of his problems solved, he said, that's great, but where's the book proof? So what he wanted to see was the most elegant proof available. Another thing we didn't mention is one of his most famous achievements, which was to be one of the two people who solved,

or came up with what's called an elementary proof of the prime number theorem. So the prime number theorem, it gives you a very accurate formula for how many primes there are up to any given number. But it was proved using techniques from a branch of mathematics called complex analysis, which is quite an advanced area. And so I mentioned earlier that Erdush proved Chebyshev's theorem using just A-level style mathematics. And the question arose. There's no obvious reason for needing to use complex numbers in order to prove facts about primes.

And so people wondered whether there was what they would call an elementary proof of the prime number theorem. roof that did not require tools like complex analysis. And this was done by, eventually by Erdus and Selberg. Unfortunately, I can't mention that without also mentioning, that this led to a very bitter priority dispute about whose role, who did exactly what. And, well, rather, actually, that's not quite accurate. I think everybody knew exactly who did what, but how that should be written up in papers,

whether they should write two separate papers Selberg with his contribution and Erdos with his contribution or whether they should combine, that led to a huge amount of bitterness. I think Erdos just wanted to, he took the attitude, which is quite common, that anybody who's contributed in any way to a result becomes a co-author on a paper. But it was complicated in this case because Selberg hadn't exactly invited Erdos to collaborate and Selberg had been out of Princeton when somebody else had told Erdos about the work.

I won't say anymore. It just led to rather unpleasant and unfortunate, I think, in the end, episode in Airdush's life, but something I don't think one can, I can't really talk about Airdush without mentioning it because it's one of the things he was very well known for. Yeah, and I wanted to say a little bit more about Ramsey numbers. So we talked about how hard they are to find, but we didn't really give examples. So I showed that six people is enough to find three that all know each other or don't know each other. And it's not too hard. I do it with my undergrad to show that 18 people is

enough if you want four people that all know each other or don't know each other. So an 18 person party is definitely big enough. But as soon as we say five, the answer is not known still. It's somewhere between 43 and 49, 48, 48 now. Yes. So already by then, we don't know the answer. And Erdish once said that imagine a malevolent alien race came to attack the earth and said they would kill us all if we didn't tell them how many people had to be at a party for five them to all know each other or not know each other. If they ask that question, then the world governments, different governments of the world should all get together

and throw all the computers on the world at it and we would probably manage it. Whereas if they asked for how many people should be at a party for six to all know each other or not know each other, then a suicidal attack would be our only way to go. So it's a cheerful side of this. But I find it just remarkable that three I was able to explain in a couple of minutes, four I can do with an undergrad and five is not known. how quickly we reach the limits of our knowledge.

Maybe just a touch on that point. Part of the reason for this, right, is because, well, if we're looking at a party of six people, there's 32,768 possible parties, I think, off of my head. But when you're looking at larger party sizes, the number of parties you need to consider is growing exponentially. So this is one of the reasons this is so difficult is because for small parties, party numbers, there's little tricks, there's little ideas like the one that Colver mentioned, but when you get to larger parties, we don't really have a great strategy at the moment for solving

this problem. Yeah, I mean, the most recent breakthrough has been done by some very, very clever computing rather than by, yeah, we haven't had some major insights into how to improve that number for a long time now. Is he thought well of back in his home country? very much so yes I mean he he's regarded as somebody who founded a kind of Hungarian school of mathematics it's not true that all Hungarians do erdoch style mathematics but it's not that far off being true so I think some have kind of maybe quite deliberately decided they're going to try to do something else but a very very large number of people in Hungary were in his immediate circle or in the circle of people who were in his immediate circle and he's had an absolutely enormous influence on Hungarian

And have they relaxed a Jewish scholars welcome there now or what? Yes, but maybe let's come back to something a little bit earlier, which is that Hungary was proud enough of him that he was granted during the Cold War a very special type of passport, which he was the only person to possess, which enabled him to both enter and leave Hungary, because they were proud enough of his mathematical achievements that despite living some of the time in America, time in Israel he was allowed in and out again. So I think that's a measure of the pride there was in him. He wound up almost boycotting his own 60th birthday conference though in Hungary because the Israeli delegation was not allowed in. He did in the end attend his conference briefly but then

didn't go back to Hungary for some years after that. So there's been ups and downs, shall we say, in the relationship there, but the proud, the national pride in Erdush is immense. Did he do work in Israel, did he continue his work there? He certainly spent a significant amount of time in Israel at one point in his life. And it is also true that a large number of Israeli mathematicians also work

in what you might call Erdoch style mathematics. There's a lot of very important contributions have been made by to graph theory, for example, by Israeli mathematicians. Yeah, so he was granted an Israeli passport and he did have a permanent post in Israel but under the understanding that he didn't have

spend very much time there. So he would go back when he wanted to for a bit. Okay. Anything, any burning issue? I can say something a bit trivial. There hasn't been enough cylinder in this program. So I came here, Melvin, under false pretenses, because as well as an airditch number, there's a bacon number.

And I looked up earlier, and you have a bacon number of three. So a bacon number is, so if you're Kevin Bacon, you have a bacon number of zero. If you've worked with Kevin Bacon, you have a bacon number of one, and so on and so forth. So now by doing this show, I have a bacon number of four,

so my Erdish bacon number is six, which is the sum of the two numbers. So I'm very pleased, so thank you very much. Anytime I want your number pushed up, just give us a show. It's a nice seven. Mine six. Okay, well, thank you all very much.

Tea or coffee? I'll have some tea, please. Not for tea, please. Not for me, thanks. Radio Podcasts. Introducing gaslight. I think there's something peculiar about this house. A new drama from BBC Radio 4.

The gas lights over there above the fireplace. Yes. I wonder if Mummy might be trying to get in touch. Is the light playing tricks on you? Or is it just your mind? What if we both sold this place and you got a job in one of those little colleges that would be pleased to have you? You don't really believe that, do you?

I'm trying to. To be kind. Like you were with the dog. How much do we really know about the person we love? Is there something I should know about, Jack? No. I didn't put a foot wrong. And how much can we rely?

Quite a bit younger than you appear to be on screen. On the kindness of strangers. And you look like you've been crying. Gaslight. You can't talk to me like that. I don't even know who you are. Available on BBC Sounds.