Paul Erdős

20 results back to index

pages: 247 words: 43,430

Think Complexity by Allen B. Downey


Benoit Mandelbrot, cellular automata, Conway's Game of Life, Craig Reynolds: boids flock, discrete time,, Frank Gehry, Gini coefficient, Guggenheim Bilbao, mandelbrot fractal, Occupy movement, Paul Erdős, sorting algorithm, stochastic process, strong AI, Thomas Kuhn: the structure of scientific revolutions, Turing complete, Turing machine, We are the 99%

You can use a queue or a “worklist” to keep them in order. Here’s how it works: Start with any vertex and add it to the queue. Remove a vertex from the queue and mark it. If it is connected to any unmarked vertices, add them to the queue. If the queue is not empty, go back to Step 2. Example 2-5. Write a Graph method named is_connected that returns True if the Graph is connected and False otherwise. Paul Erdős: Peripatetic Mathematician, Speed Freak Paul Erdős was a Hungarian mathematician who spent most of his career (from 1934 until his death in 1992) living out of a suitcase, visiting colleagues at universities all over the world, and authoring papers with more than 500 collaborators. He was a notorious caffeine addict and, for the last 20 years of his life, an enthusiastic user of amphetamines. He attributed at least some of his productivity to the use of these drugs; after giving them up for a month to win a bet, he complained that the only result was that mathematics had been set back by a month.[3] In the 1960s, he and Alfréd Rényi wrote a series of papers introducing the Erdős-Rényi model of random graphs and studying their properties.

Think Complexity Table of Contents Preface Why I Wrote This Book Suggestions for Teachers Suggestions for Autodidacts Contributor List Conventions Used in This Book Using Code Examples Safari® Books Online How to Contact Us 1. Complexity Science What Is This Book About? A New Kind of Science Paradigm Shift? The Axes of Scientific Models A New Kind of Model A New Kind of Engineering A New Kind of Thinking 2. Graphs What’s a Graph? Representing Graphs Random Graphs Connected Graphs Paul Erdős: Peripatetic Mathematician, Speed Freak Iterators Generators 3. Analysis of Algorithms Order of Growth Analysis of Basic Python Operations Analysis of Search Algorithms Hashtables Summing Lists pyplot List Comprehensions 4. Small World Graphs Analysis of Graph Algorithms FIFO Implementation Stanley Milgram Watts and Strogatz Dijkstra What Kind of Explanation Is That? 5.

For a given size n, there is a critical value, , such that a random graph is unlikely to be connected if and very likely to be connected if . Write a program that tests this result by generating random graphs for values of n and p, and then computing the fraction of the values that are connected. How does the abruptness of the transition depend on n? You can download my solution from * * * [3] Much of this biography follows Iterators If you have read the documentation of Python dictionaries, you might have noticed the methods iterkeys, itervalues, and iteritems. These methods are similar to keys, values, and items except that instead of building a new list, they return iterators. An iterator is an object that provides a method named next that returns the next element in a sequence. Here is an example that creates a dictionary and uses iterkeys to traverse the keys. >>> d = dict(a=1, b=2) >>> iter = d.iterkeys() >>> print a >>> print b >>> print Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration The first time next is invoked, it returns the first key from the dictionary (the order of the keys is arbitrary).


pages: 94 words: 26,453

The End of Nice: How to Be Human in a World Run by Robots (Kindle Single) by Richard Newton


3D printing, Black Swan, British Empire, Buckminster Fuller, Clayton Christensen, crowdsourcing, deliberate practice, fear of failure, Filter Bubble, future of work, Google Glasses, Isaac Newton, James Dyson, Jaron Lanier, Jeff Bezos, job automation, Lean Startup, low skilled workers, Mark Zuckerberg, move fast and break things, Paul Erdős, Paul Graham, recommendation engine, rising living standards, Robert Shiller, Robert Shiller, Silicon Valley, Silicon Valley startup, skunkworks, Steve Ballmer, Steve Jobs, Y Combinator

Seeing sideways How should we go about this? How do we think different and push back against the pressure to conform? How do iconoclasts, artists and innovators approach the world? The greatest mathematician of his generation, Paul Erdos, would turn up at the houses of friends ready to discuss big, new ideas. While most mathematicians might hope to publish say fifty papers in their entire career, he was publishing fifty a year in his 80s. He collaborated with more people in the field of mathematics than anyone who has ever lived. According to Paul Hoffman, author of The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth, “his modus operandi was to show up on the doorstep of a fellow mathematician, declare ‘My brain is open’, work with his host for a day or two, until he was bored or his host was run down, and then move to another home”.

But if they try saying in and out for a few days in fun, they find themselves beginning to realise that they are indeed going inward and outward in respect to the center of Earth, which is our Spaceship Earth. And for the first time they begin to feel real ‘reality’.” As you know, it didn’t catch on. But it demonstrates the fierce independence of thought that gave him the ability to see and think differently. Paul Erdos and Buckminster Fuller perceived the world differently and so they used different words to label everyday activities and this in turn helped them approach problems and opportunity differently. Now, if you apply such different thinking to the fast-growing entrepreneurial business in the world we live in right now you might get “The Offer”. Zappos, the disruptive, fast-growing online shoe company doesn’t conform to much.

As Jones says: “Without sufficient understanding of other fields, how is anyone to understand the potential applications, in those fields, of discoveries within their own?” Notice things The art of Anti-Order is to notice things that may be outside your normal channels. In order to spot how and where your knowledge can be applied to novel and valuable effect you need to have your head up and your mind open, as Paul Erdos would say. Professor Alexander Fleming once noticed something that saved hundreds of millions of lives. The roots of it can be found in his very unusual hobby. Fleming had another passion aside from his professional interest in the study of bacteria: he loved to paint. He was a self-taught painter and a member of Chelsea Arts Club. Some of his patients would even give him paintings in exchange for treatment.


pages: 262 words: 65,959

The Simpsons and Their Mathematical Secrets by Simon Singh


Albert Einstein, Andrew Wiles, Benoit Mandelbrot, cognitive dissonance, Erdős number, Georg Cantor, Grace Hopper, Isaac Newton, John Nash: game theory, mandelbrot fractal, Menlo Park, Norbert Wiener, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, Richard Feynman, Richard Feynman, Schrödinger's Cat, Simon Singh, Stephen Hawking, Wolfskehl Prize, women in the workforce

This is the most general and best-known version of six degrees of separation, but the technique can be adapted to specific communities, such as mathematicians. Hence, six degrees of separation can be used to identify who is well connected in the world of mathematics, and who, therefore, might have the best mathematical credentials. It is not a perfect measurement, but it can offer some interesting insights. The mathematical version of six degrees of separation is called six degrees of Paul Erdős, named after the mathematician Paul Erdős (1913–96). The goal is to find a connection between any given mathematician and Erdős, and mathematicians with closer connections are then ranked higher than those with more tenuous connections. But why is Erdős considered to be at the center of the mathematical universe? Erdős holds this position because he was the most prolific mathematician of the twentieth century. He published 1,525 research papers, which he wrote with 511 co-authors.

Throughout his life, he was able to fit all his belongings into a single suitcase, which was very convenient for a nomadic mathematician constantly on the road in search of the most interesting problems and the most fruitful collaborations. He fueled his brain with coffee and amphetamines in order to maximize his mathematical output, and he often repeated a notion first posited by his colleague Alfréd Rényi: “A mathematician is a machine for turning coffee into theorems.” In six degrees of Paul Erdős, connections are made via co-authored articles, typically mathematical research papers. Anybody who has co-authored a paper directly with Erdős is said to have an Erdős number of 1. Similarly, mathematicians who have co-authored a paper with someone who has co-authored a paper with Erdős are said to have an Erdős number of 2, and so on. Via one chain or another, Erdős can be connected to almost any mathematician in the world, regardless of their field of research.

So, how does Jeff Westbrook rank in terms of his Erdős number? He started publishing research papers while working on his PhD in computer science at Princeton University. As well as writing his 1989 thesis, titled “Algorithms and Data Structures for Dynamic Graph Algorithms,” he co-authored papers with his supervisor Robert Tarjan. In turn, Tarjan has published with Maria Klawe, who collaborated with Paul Erdős. This gives Westbrook a very respectable Erdős number of just 3. However, this does not make him a clear winner among the writers on The Simpsons. David S. Cohen has published a paper with Manuel Blum, another Turing Award winner, who in turn has published a paper with Noga Alon at Tel Aviv University, who in turn published several papers with Erdős. Hence, Cohen can also claim an Erdős number of 3.


pages: 349 words: 95,972

Messy: The Power of Disorder to Transform Our Lives by Tim Harford


affirmative action, Air France Flight 447, Airbnb, airport security, Albert Einstein, Amazon Mechanical Turk, Amazon Web Services, Atul Gawande, autonomous vehicles, banking crisis, Barry Marshall: ulcers, Basel III, Berlin Wall, British Empire, Broken windows theory, call centre, Cass Sunstein, Chris Urmson, cloud computing, collateralized debt obligation, crowdsourcing, deindustrialization, Donald Trump, Erdős number, experimental subject, Ferguson, Missouri, Filter Bubble, Frank Gehry, game design, global supply chain, Googley, Guggenheim Bilbao, high net worth, Inbox Zero, income inequality, Internet of things, Jane Jacobs, Jeff Bezos, Loebner Prize, Louis Pasteur, Mark Zuckerberg, Menlo Park, Merlin Mann, microbiome, out of africa, Paul Erdős, Richard Thaler, Rosa Parks, self-driving car, side project, Silicon Valley, Silicon Valley startup, Skype, Steve Jobs, Steven Levy, Stewart Brand, telemarketer, the built environment, The Death and Life of Great American Cities, Turing test, urban decay

He couldn’t even pack his own suitcase. People found him impossibly demanding; it was like caring for an infant.9 And yet, everyone loved working with him. Years after his death, papers continued to be published listing Paul Erdős as a coauthor, as the seeds he planted continued to bear fruit. • • • Sociologists have a term for these different kinds of collaboration. When Hunt-Davis and his crewmates focused purely on one another and the task ahead of them, cutting themselves off from the temptations of the outside world, they were building up their “bonding social capital.” Paul Erdős restlessly traversed that outside world with a plastic bag full of the latest mathematical offprints, bringing news from Beijing to Princeton to Manchester to Budapest—and from set theory to number theory to probability theory and back—and created “bridging social capital.”

Version_1 To Stella, Africa, and Herbie—masters of mess Contents Title Page Copyright Dedication Introduction “It was unplayable.” 1. Creativity “You’re asking the blood in your brain to flow in another direction.” Bowie, Eno, and Darwin: How Frustration and Distraction Help Us Solve Problems in Art, Science, and Life 2. Collaboration “My brain is open!” Paul Erdős and the Robbers Cave: Why Tidy Teams Have More Fun but Messy Teamwork Gets More Done 3. Workplaces “Nobody cares what you do in there.” Where Steve Jobs Went Wrong, and Why It’s Nobody Else’s Business Whether You Tidy Your Desk 4. Improvisation “You ain’t got much time to think, ’cause you in the chair from now on.” Martin Luther King, the Help Desk, and the Unexpected Benefits of Letting Go of the Script 5.

“But quite honestly it did take me out of my comfort zone and it did make me leave my frustration at what I was doing and totally look at it from another different point of view and although I didn’t like the point of view, when I came back, I was fresh.”41 Alomar now teaches music at the Stevens Institute of Technology in New Jersey, and he regularly resorts to the Oblique Strategies. His students will sometimes experience creative block, and “I need for them to see what I saw, and feel what I felt, and the dilemma that I had when I had to come up with something out of nothing.”42 He adds, “They’re very curious cards.” When I tell Brian Eno this, he laughs. 2 Collaboration “My brain is open!” Paul Erdős and the Robbers Cave: Why Tidy Teams Have More Fun but Messy Teamwork Gets More Done In 1999, as the Summer Olympics in Sydney approached, Ben Hunt-Davis was tantalizingly short of being one of the best rowers in the world. The British rowing team was built around one of the greatest Olympians of any era, Steve Redgrave, a man who was targeting the scarcely believable feat of winning a gold medal in a fifth consecutive Olympic games.


pages: 434 words: 135,226

The Music of the Primes by Marcus Du Sautoy


Ada Lovelace, Andrew Wiles, Arthur Eddington, Augustin-Louis Cauchy, computer age, Dava Sobel, Dmitri Mendeleev, Eratosthenes, Erdős number, four colour theorem, Georg Cantor, German hyperinflation, global village, Henri Poincaré, Isaac Newton, Jacquard loom, Jacquard loom, music of the spheres, New Journalism, Paul Erdős, Richard Feynman, Richard Feynman, Search for Extraterrestrial Intelligence, Simon Singh, Solar eclipse in 1919, Stephen Hawking, Turing machine, William of Occam, Wolfskehl Prize, Y2K

Alexanderson (Boston: Birkhäuser, 1985), pp. 66–79 Aldous, D., and Diaconis, P., ‘Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem’, Bulletin of the American Mathematical Society, vol. 36, no. 4 (1999), pp. 413–32 Alexanderson, G.L., Interview with Paul Erdos, in Mathematical People: Profiles and Interviews, ed. D.J. Albers and G.L. Alexanderson (Boston: Birkhäuser, 1985), pp. 82–91 Babai, L., Pomerance, C., and Vértesi, P., ‘The mathematics of Paul Erdos’, Notices of the American Mathematical Society, vol. 45, no. 1 (1998), pp. 19–31 Babai, L., and Spencer, J., ‘Paul Erdos (1913–1996)’, Notices of the American Mathematical Society, vol. 45, no. 1 (1998), pp. 64–73 Barner, K., ‘Paul Wolfskehl and the Wolfskehl Prize’, Notices of the American Mathematical Society, vol. 44, no. 10 (1997), pp. 1294–1303 Beiler, A.H., Recreations in the Theory of Numbers: The Queen of Mathematics Entertains (New York: Dover Publications, 1964) Bell, E.T., Men of Mathematics (New York: Simon & Schuster, 1937) Berndt, B.C., and Rankin, R.A.

Not only had they accepted Göttingen’s mathematicians, but they appeared to have appropriated the German town’s motto: for members of the Institute, there was no life outside Princeton. Isolated in the woods, the Institute provided the perfect working environment for banished and fleeing Europeans. Erdos, the wizard from Budapest There was another mathematical émigré from Europe at the Institute whose life was to become intertwined with Selberg’s. While Ramanujan’s story had been inspiring the young Selberg in Norway, its magic was also working on another young mind. Paul Erdos, a Hungarian, was to become one of the most intriguing mathematicians of the second half of the twentieth century. But Ramanujan would not be the only thing to link these two young mathematicians. There was also controversy. Whereas Selberg liked to work alone, Erdos thrived on collaboration. His stooped figure, clad in sandals and a suit, was familiar in mathematical common rooms across the world.

For example, does the computer search for big primes give us any better understanding of the primes? We might be able to sing higher and higher notes, but the music remains hidden. Euclid has already assured us that there will always be a bigger prime to find. It isn’t known, though, whether Mersenne’s special numbers will produce primes infinitely often. It may be that Michael Cameron has discovered the thirty-ninth and final Mersenne prime. When I talked to Paul Erdos, he ranked the task of proving that there are infinitely many Mersenne primes as one of the greatest unsolved problems of number theory. It is generally believed that there are infinitely many choices of n that make 2n − 1 prime. But it is very unlikely that a computer will prove it. That’s not to say that computers can’t prove things. Given a set of axioms and rules of deduction, you can program a computer to start churning out mathematical theorems.


pages: 266 words: 86,324

The Drunkard's Walk: How Randomness Rules Our Lives by Leonard Mlodinow


Albert Einstein, Alfred Russel Wallace, Antoine Gombaud: Chevalier de Méré, Atul Gawande, Brownian motion, butterfly effect, correlation coefficient, Daniel Kahneman / Amos Tversky, Donald Trump, feminist movement, forensic accounting, Gerolamo Cardano, Henri Poincaré, index fund, Isaac Newton, law of one price, pattern recognition, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, RAND corporation, random walk, Richard Feynman, Richard Feynman, Ronald Reagan, Stephen Hawking, Steve Jobs, The Wealth of Nations by Adam Smith, The Wisdom of Crowds, V2 rocket, Watson beat the top human players on Jeopardy!

Army Research Institute remarked, “If all those PhDs are wrong the country would be in serious trouble.” Responses continued in such great numbers and for such a long time that after devoting quite a bit of column space to the issue, Marilyn decided she would no longer address it. The army PhD who wrote in may have been correct that if all those PhDs were wrong, it would be a sign of trouble. But Marilyn was correct. When told of this, Paul Erdös, one of the leading mathematicians of the twentieth century, said, “That’s impossible.” Then, when presented with a formal mathematical proof of the correct answer, he still didn’t believe it and grew angry. Only after a colleague arranged for a computer simulation in which Erdös watched hundreds of trials that came out 2 to 1 in favor of switching did Erdös concede he was wrong.6 How can something that seems so obvious be wrong?

After he is done, the chances are still 1 in 100 that the Maserati was behind the door you chose and still 99 in 100 that it was behind one of the other doors. But now, thanks to the intervention of the host, there is only one door left representing all 99 of those other doors, and so the probability that the Maserati is behind that remaining door is 99 out of 100! Had the Monty Hall problem been around in Cardano’s day, would he have been a Marilyn vos Savant or a Paul Erdös? The law of the sample space handles the problem nicely, but we have no way of knowing for sure, for the earliest known statement of the problem (under a different name) didn’t occur until 1959, in an article by Martin Gardner in Scientific American.16 Gardner called it “a wonderfully confusing little problem” and noted that “in no other branch of mathematics is it so easy for experts to blunder as in probability theory.”

.: Lawrence Erlbaum Associates, 2003), p. 198. 4. National Science Board, Science and Engineering Indicators—2002 (Arlington, Va.: National Science Foundation, 2002); See vol. 2, chap. 7, table 7-10. 5. Gary P. Posner, “Nation’s Mathematicians Guilty of Innumeracy,” Skeptical Inquirer 15, no. 4 (Summer 1991). 6. Bruce Schechter, My Brain Is Open: The Mathematical Journeys of Paul Erdös (New York: Touchstone, 1998), pp. 107–9. 7. Ibid., pp. 189–90, 196–97. 8. John Tierney, “Behind Monty’s Doors: Puzzle, Debate and Answer?” New York Times, July 21, 1991. 9. Robert S. Gottfried, The Black Death: Natural and Human Disaster in Medieval Europe (New York: Free Press, 1985). 10. Gerolamo Cardano, quoted in Wykes, Doctor Cardano, p. 18. 11. Kline, Mathematical Thought, pp. 184–85, 259–60. 12.


pages: 379 words: 113,656

Six Degrees: The Science of a Connected Age by Duncan J. Watts


Berlin Wall, Bretton Woods, business process, corporate governance, Drosophila, Erdős number, experimental subject, Frank Gehry, Geoffrey West, Santa Fe Institute, invisible hand, Long Term Capital Management, market bubble, Milgram experiment, Murray Gell-Mann, Network effects, new economy, Norbert Wiener, Paul Erdős, rolodex, Ronald Coase, Silicon Valley, supply-chain management, The Nature of the Firm, The Wealth of Nations by Adam Smith, Toyota Production System, transaction costs, transcontinental railway, Y2K

Although in making such a drastic simplification, we inevitably miss features of the world that we ultimately care about, we can tap into a wealth of knowledge and techniques that will enable us to address a set of very general questions about networks that we might never have been able to answer had we gotten bogged down in all the messy details. CHAPTER TWO The Origins of a “New” Science THE THEORY OF RANDOM GRAPHS ABOUT FORTY YEARS AGO, THE MATHEMATICIAN PAUL ERDOS took a particularly simple approach to the study of communication networks. Erdos was the kind of unusual figure who makes other oddballs look positively vanilla. Born in Budapest on March 26, 1913, Erdos lived with his mother until he was twenty-one, then spent the rest of his remarkable life living out of two battered suitcases. Never staying anywhere for long and never holding a permanent job, Erdos relied on the hospitality of his devoted colleagues, who were more than happy to oblige him in return for the company of his lightning-fast, ever questioning mind.

The network of movie actors is also an affiliation network consisting of actors on the one hand and movies on the other. By acting together in a movie, two actors are considered affiliated. A similar description can be applied to corporate directors who sit together on boards of companies, and scientists who write papers together. In fact, one of the earliest affiliation networks to receive any attention was the coauthorship network of mathematicians that includes Paul Erdos, the inventor of random graph theory who we encountered in chapter 2. Another reason to study affiliation networks is that the data we have are unusually good because at least for contexts like membership in clubs, participation in business activities, and collaboration on joint projects like movies or scientific papers, it is particularly clear who belongs to what. Recently, a great deal of such data has become available electronically in the form of on-line databases, so even very large networks can be constructed and analyzed rapidly.

Even if in theory you are only six degrees away from anybody else in the world, there are still six billion people in the world and at least that many paths leading to them. Confronted with this maze of mind-boggling complexity, how are we to find the one short path that we are seeking? Well, it’s hard—at least on your own. Long before the Kevin Bacon Game came along, mathematicians used to play a similar game with Paul Erdos. Erdos, being not only a great (and extremely prolific) mathematician but also something of a celebrity in the mathematics community, was thought to be the center of the math world in much the same way that Bacon was for the world of movie actors. As a result, if you have published a paper with Erdos, you get to have an Erdos number of one. If you haven’t published a paper with Erdos but you have written one with someone who has, then you have an Erdos number of two.


pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow


Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Richard Feynman, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

For example, the shortest route from Charlie Chaplin to Kevin Bacon has length three: Chaplin directed and had a small acting role in the 1967 movie A Countess from Hong Kong, with Sophia Loren as the countess. Sophia Loren starred in the little-known 1979 flick Firepower. Eli Wallach had a major role in Firepower and a tiny uncredited role in Mystic River with Kevin Bacon. Mathematicians have a similar game for having co-written papers centering on the highly prolific combinatorialist Paul Erdős.* The researchers at the Institute first decided to check the six-degrees rule for friendships in Frenemy. To check whether Alice and George have a chain of length six between them, one simple approach is to try all possible chains of length six between them. But there are 3,198,400,279,980,000,480,000 possible chains of length six through the 20,000 inhabitants of Frenemy, which would take more than 100 years even if a computer could check a trillion chains a second.

This is why mathematicians derive fame from finding clever ways to prove mathematical statements. It can even be difficult to find ways to make simple logical expressions true. From that problem came a theory that links most of the NP problems together, a story we tell in the next chapter. A Solution to the Icosian Game Figure 3-18. Icosian Solution. * I have written papers with three different co-authors of Paul Erdős, giving me an Erdős number of 2. With Erdős’s 1996 passing, my chances of reducing my Erdős number are slim. I have had no acting experience (or talent) and do not have a Bacon number. Chapter 4 THE HARDEST PROBLEMS IN NP A psychologist decides to run an experiment with a mathematician. The psychologist puts the mathematician in a one-room wooden hut that has some kindling on the floor, a table, and a bucket of water on the table.


pages: 295 words: 66,824

A Mathematician Plays the Stock Market by John Allen Paulos


Benoit Mandelbrot, Black-Scholes formula, Brownian motion, business climate, butterfly effect, capital asset pricing model, correlation coefficient, correlation does not imply causation, Daniel Kahneman / Amos Tversky, diversified portfolio, Donald Trump, double entry bookkeeping, Elliott wave, endowment effect, Erdős number, Eugene Fama: efficient market hypothesis, four colour theorem, George Gilder, global village, greed is good, index fund, invisible hand, Isaac Newton, John Nash: game theory, Long Term Capital Management, loss aversion, Louis Bachelier, mandelbrot fractal, margin call, mental accounting, Nash equilibrium, Network effects, passive investing, Paul Erdős, Ponzi scheme, price anchoring, Ralph Nelson Elliott, random walk, Richard Thaler, Robert Shiller, Robert Shiller, short selling, six sigma, Stephen Hawking, transaction costs, ultimatum game, Vanguard fund, Yogi Berra

Imagine the Andersen accountants muttering anxiously that there weren’t enough leading “1s” on the documents they were feeding into the shredders. A 1-derful fantasy! The Numbers Man—A Screen Treatment An astonishing amount of attention has been paid recently to fictional and narrative treatments of mathematical topics. The movies Good Will Hunting, Pi, and The Croupier come to mind; so do plays such as Copenhagen, Arcadia, and The Proof, the two biographies of Paul Erdos, A Beautiful Mind, the biography of John Nash (with its accompanying Academy Award-winning movie), TV specials on Fermat’s Last Theorem, and other mathematical topics, as well as countless books on popular mathematics and mathematicians. The plays and movies, in particular, prompted me to expand the idea in the stock-newsletter scam discussed above (I changed the focus, however, from stocks to sports) into a sort of abbreviated screen treatment that highlights the relevant mathematics a bit more than has been the case in the productions just cited.

(Actually, under reasonable assumptions each of us is connected to everyone else by an average of two links, although we’re not likely to know who the two intermediate parties are.) Another popular variant of the notion concerns the number of movie links between film actors, say between Marlon Brando and Christina Ricci or between Kevin Bacon and anyone else. If A and B appeared together in X, and B and C appeared together in Y, then A is linked to C via these two movies. Although they may not know of Kevin Bacon and his movies, most mathematicians are familiar with Paul Erdös and his theorems. Erdös, a prolific and peripatetic Hungarian mathematician, wrote hundreds of papers in a variety of mathematical areas during his long life. Many of these had co-authors, who are therefore said to have Erdös number 1. Mathematicians who have written a joint paper with someone with Erdös number 1 are said to have Erdos number 2, and so on. Ideas about such informal networks lead naturally to the network of all networks, the Internet, and to ways to analyze its structure, shape, and “diameter.”


pages: 210 words: 62,771

Turing's Vision: The Birth of Computer Science by Chris Bernhardt


Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, British Empire, cellular automata, Claude Shannon: information theory, complexity theory, Conway's Game of Life, discrete time, Douglas Hofstadter, Georg Cantor, Gödel, Escher, Bach, Henri Poincaré, Internet Archive, Jacquard loom, Jacquard loom, John Conway, John von Neumann, Joseph-Marie Jacquard, Norbert Wiener, Paul Erdős, Turing complete, Turing machine, Turing test, Von Neumann architecture

Turing’s argument was remarkably simple and elegant. His paper was not published for the result, but for the proof of the result. Mathematicians often describe proofs in terms of beauty. When doing mathematics there is an aesthetic that guides. At times you have a proof, but feel that it is clumsy and that there must be a better one that needs to be found. This is what the Hungarian mathematician Paul Erdős was referring to when he talked about The Book. According to Erdős, there is a book in which God had written down all the shortest, most beautiful proofs. Erdős famously said “You don’t have to believe in God, but you should believe in The Book.” Turing’s proofs, along with those of Gödel and Georg Cantor on which they are based, are definitely in The Book. This book is for the reader who wants to understand these ideas.


pages: 212 words: 68,754

Thinking in Numbers by Daniel Tammet


Albert Einstein, Alfred Russel Wallace, Anton Chekhov, computer age, dematerialisation, Edmond Halley, four colour theorem, Georg Cantor, index card, Isaac Newton, Paul Erdős, Searching for Interstellar Communications

It is a mostly thankless task to try to assign to mathematicians some universal trait. Einstein’s famous predilection for beauty offers one rare exception. Mathematicians can be tall or short, worldly or remote, bookworms or book-burners, multilingual or monosyllabic, tone-deaf or musically gifted, devout or irreligious, hermit or activist, but virtually all would agree with the Hungarian mathematician Paul Erdos when he said, ‘I know numbers are beautiful. If they are not beautiful, nothing is.’ Einstein was a physicist, yet his equations inspired the interest and admiration of many mathematicians. His theory of relativity drew their praise for combining great elegance with economy. In a handful of succinct formulas, every symbol and every number obtaining its perfect weight, Newtonian time and space were recast.


pages: 284 words: 79,265

The Half-Life of Facts: Why Everything We Know Has an Expiration Date by Samuel Arbesman


Albert Einstein, Alfred Russel Wallace, Amazon Mechanical Turk, Andrew Wiles, bioinformatics, British Empire, Chelsea Manning, Clayton Christensen, cognitive bias, cognitive dissonance, conceptual framework, David Brooks, demographic transition, double entry bookkeeping, double helix, Galaxy Zoo, guest worker program, Gödel, Escher, Bach, Ignaz Semmelweis: hand washing, index fund, invention of movable type, Isaac Newton, John Harrison: Longitude, Kevin Kelly, life extension, meta analysis, meta-analysis, Milgram experiment, Nicholas Carr, p-value, Paul Erdős, Pluto: dwarf planet, randomized controlled trial, Richard Feynman, Richard Feynman, Rodney Brooks, social graph, social web, text mining, the scientific method, Thomas Kuhn: the structure of scientific revolutions, Thomas Malthus, Tyler Cowen: Great Stagnation

They explored how these models have been reinvented again and again, and they go into great detail, over the course of thirty-five pages, eventually summarizing these successive reinventions in a large table. They show, for example, that something known as the branching process was discovered in the mid-1840s, only to be rediscovered in the 1870s, then again in 1922, 1930, 1938, 1941, and 1944. The Erdo˝s-Rényi random graph, written about by Paul Erdo˝s and Alfréd Rényi in 1960, was first examined in 1941 by Paul Flory, the chemist and Nobel laureate. As Stigler’s Law of Eponymy states: “No scientific law is named after its discoverer.” Naturally, Stephen Stigler attributes this law to Robert Merton. Extreme cases of this can especially be found during times of war. Richard Feynman, the celebrated physicist, shared the Nobel Prize with two other physicists, including Sin-Itiro Tomonaga.


pages: 998 words: 211,235

A Beautiful Mind by Sylvia Nasar


Al Roth, Albert Einstein, Andrew Wiles, Brownian motion, cognitive dissonance, Columbine, experimental economics, fear of failure, Henri Poincaré, invisible hand, Isaac Newton, John Conway, John Nash: game theory, John von Neumann, Kenneth Rogoff, linear programming, lone genius, market design, medical residency, Nash equilibrium, Norbert Wiener, Paul Erdős, prisoner's dilemma, RAND corporation, Ronald Coase, second-price auction, Silicon Valley, Simon Singh, spectrum auction, The Wealth of Nations by Adam Smith, Thorstein Veblen, upwardly mobile

“Johnny came back with the solution the following week. I gave another one that week and a week later he had that solution too. It was extraordinary.” Johnny wrote a joint paper with Nathanson that became the first chapter of his dissertation.49 He then wrote a second paper on his own, which Nathanson called “beautiful” and which also became part of the thesis.50 His third paper was an important generalization of a theorem proved by Paul Erdos in the 1930s for a special case of so-called B sequences.51 Neither Erdos nor anyone else had succeeded in proving that the theorem held for other sequences, and Johnny’s successful attack on the problem would generate a flurry of papers by other number theorists. When Johnny got his Ph.D. from Rutgers in 1985, said Nathanson, he seemed poised for a long and productive career as a first-rate research mathematician.

Letter from J. Nash to L. Hörmander, from Paris, 1.18.60. 51. Postcard from J. Nash to V. Nash, 10.11.59. 52. After returning to the U.S., Nash claimed to be a resident of Liechtenstein, which levied no income tax, and refused to sign U.S. tax forms (source: H. Kuhn, interview, 8.92). 53. O. Larde, interview, 12.8.96. 54. Letter from John Nash to Virginia Nash, 11.10.59. 55. The anecdote concerns Paul Erdos and was told by Donald Spencer, interview, 11.28.95. 56. O. Larde, interview, 12.8.95. 57. M. Legg, interview, 3.29.96. 58. Sass, op. cit. 59. Letter from John Nash to Norbert Wiener, 12.9.95. 60. Letter from J. Nash to V. Nash, 12.13.59. 61. Franz Kafka, The Metamorphosis (New York: Schocken Books, 1995). 62. Irving Howe introduction, Kafka, The Castle, op. cit. 63. James M. Glass, Delusion (Chicago: University of Chicago Press, 1985). 64.


pages: 626 words: 181,434

I Am a Strange Loop by Douglas R. Hofstadter


Albert Einstein, Andrew Wiles, Benoit Mandelbrot, Brownian motion, double helix, Douglas Hofstadter, Georg Cantor, Gödel, Escher, Bach, Isaac Newton, James Watt: steam engine, John Conway, John von Neumann, mandelbrot fractal, pattern recognition, Paul Erdős, place-making, probability theory / Blaise Pascal / Pierre de Fermat, publish or perish, random walk, Ronald Reagan, self-driving car, Silicon Valley, telepresence, Turing machine

The existence of a perfect pattern, a regularity that goes on forever, reveals — just as smoke reveals a fire — that something is going on behind the scenes. Mathematicians consider it a sacred goal to seek that thing, uncover it, and bring it out into the open. This activity is called, as you well know, “finding a proof ”, or stated otherwise, turning a conjecture into a theorem. The late great eccentric Hungarian mathematician Paul Erdös once made the droll remark that “a mathematician is a device for turning coffee into theorems”, and although there is surely truth in his witticism, it would be more accurate to say that mathematicians are devices for finding conjectures and turning them into theorems. What underlies the mathematical mindset is an unshakable belief that whenever some mathematical statement X is true, then X has a proof, and vice versa.

Page 114 the sum of two squares… See [Hardy and Wright] and [Niven and Zuckerman]. Page 114 the sum of two primes… See [Wells 2005], an exquisite garden of delights. Page 116 The passionate quest after order in an apparent disorder is what lights their fires… See [Ulam], [Ash and Gross], [Wells 2005], [Gardner], [Bewersdorff ], and [Livio]. Page 117 Nothing happens “by accident” in the world of mathematics… See [Davies]. Page 118 Paul Erdös once made the droll remark… Erdös, a devout matheist, often spoke of proofs from “The Book”, an imagined tome containing God’s perfect proofs of all great truths. For my own vision of “matheism”, see Chapter 1 of [Hofstadter and FARG]. Page 119 Variations on a Theme by Euclid… See [Chaitin]. Page 120 God does not play dice… See [Hoffmann], one of the best books I have ever read. Page 121 many textbooks of number theory prove this theorem… See [Hardy and Wright] and [Niven and Zuckerman].


pages: 518 words: 107,836

How Not to Network a Nation: The Uneasy History of the Soviet Internet (Information Policy) by Benjamin Peters


Albert Einstein, Andrei Shleifer, Benoit Mandelbrot, bitcoin, Brownian motion, Claude Shannon: information theory, cloud computing, cognitive dissonance, computer age, conceptual framework, crony capitalism, crowdsourcing, cuban missile crisis, Daniel Kahneman / Amos Tversky, David Graeber, Dissolution of the Soviet Union, double helix, Drosophila, Francis Fukuyama: the end of history, From Mathematics to the Technologies of Life and Death, hive mind, index card, informal economy, invisible hand, Jacquard loom, Jacquard loom, John von Neumann, Kevin Kelly, knowledge economy, knowledge worker, linear programming, mandelbrot fractal, Marshall McLuhan, means of production, Menlo Park, Mikhail Gorbachev, mutually assured destruction, Network effects, Norbert Wiener, packet switching, pattern recognition, Paul Erdős, Peter Thiel, RAND corporation, rent-seeking, road to serfdom, Ronald Coase, scientific mainstream, Steve Jobs, Stewart Brand, stochastic process, technoutopianism, The Structural Transformation of the Public Sphere, transaction costs, Turing machine

Kantorovich: The Price Implications of Optimal Planning,” in Socialism and the Market: Mechanism Design Theory and the Allocation of Resources, ed. Peter J. Boettke, 638–648 (New York: Routledge, 2000). Few have satisfactorily described the forces behind the phenomenal scientific output of the generation born between 1890 and 1930 to a tiny Jewish middle class in Hungary. Members of this group include mathematician and founding computer scientist and game theorist John von Neumann; pan-prolific mathematician Paul Erdős; Nobel laureate and founder of holography Dennis Gabor; Nobel laureate and physicist Eugene Wigner; early supersonic aerospace engineer Theodore von Kármán; discoverer of the linear accelerator, the electron microscope, and nuclear chain reaction Leo Szilard; the primary force behind the hydrogen bomb Edward Teller; codeveloper of BASIC computer programming John George Kemeny; historian Oszkar Jaszi; philosopher Georg Lukacs, economist and philosopher Karl Polanyi; author Arthur Koesler; and composer Bela Bartok.


pages: 437 words: 132,041

Alex's Adventures in Numberland by Alex Bellos


Andrew Wiles, Antoine Gombaud: Chevalier de Méré, Black Swan, Black-Scholes formula, Claude Shannon: information theory, computer age, Daniel Kahneman / Amos Tversky, family office, forensic accounting, game design, Georg Cantor, Henri Poincaré, Isaac Newton, pattern recognition, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, random walk, Richard Feynman, Richard Feynman, SETI@home, Steve Jobs, The Bell Curve by Richard Herrnstein and Charles Murray, traveling salesman

., Why Do Buses Come in Threes?, Robson Books, London, 1998 Eastaway, R., and Wyndham, J., How Long is a Piece of String?, Robson Books, London, 2002 Gowers, T., Mathematics: A Very Short Introduction, Oxford University Press, Oxford, 2002 Gullberg, J., Mathematics, W. W. Norton, New York, 1997 Hodges, A., One to Nine, Short Books, London, 2007 Hoffman, P., The Man Who Loved Only Numbers: The Story of Paul Erdös and the Search for Mathematical Truth, Fourth Estate, 1998 Hogben, L., Mathematics for the Million, Allen & Unwin, London, 1936 Mazur, J., Euclid in the Rainforest, Plume, New York, 2005 Newman, J. (ed.), The World of Mathematics, Dover, New York, 1956 Pickover, C.A., A Passion for Mathematics, Wiley, Hoboken, NJ, 2005 Singh, S., Fermat’s Last Theorem, Fourth Estate, London, 1997 Acknowledgements Firstly, thanks to Claire Paterson at Janklow & Nesbit, without whose encouragement this book would never have been written, and to my editors Richard Atkinson in London and Emily Loose in New York.


pages: 442 words: 39,064

Why Stock Markets Crash: Critical Events in Complex Financial Systems by Didier Sornette


Asian financial crisis, asset allocation, Berlin Wall, Bretton Woods, Brownian motion, capital asset pricing model, capital controls, continuous double auction, currency peg, Deng Xiaoping, discrete time, diversified portfolio, Elliott wave, Erdős number, experimental economics, financial innovation, floating exchange rates, frictionless, frictionless market, full employment, global village, implied volatility, index fund, invisible hand, John von Neumann, joint-stock company, law of one price, Louis Bachelier, mandelbrot fractal, margin call, market bubble, market clearing, market design, market fundamentalism, mental accounting, moral hazard, Network effects, new economy, oil shock, open economy, pattern recognition, Paul Erdős, quantitative trading / quantitative finance, random walk, risk/return, Ronald Reagan, Schrödinger's Cat, short selling, Silicon Valley, South Sea Bubble, statistical model, stochastic process, Tacoma Narrows Bridge, technological singularity, The Coming Technological Singularity, The Wealth of Nations by Adam Smith, Tobin tax, total factor productivity, transaction costs, tulip mania, VA Linux, Y2K, yield curve

This network may represent a good proxy for professional networks such as traders and, to a lesser degree, investors. The idea is that most pairs of people who have written a scientific paper together are genuinely acquainted with one another, as they are supposed to have conducted together the research reported in the paper. The idea of networks of coauthorship is not new. Most practicing mathematicians are familiar with the definition of the Erdös number [178]. Paul Erdös (1913–1996), the widely traveled and incredibly prolific Hungarian mathematician, wrote at least 1,400 mathematical research papers in many different areas, many in collaboration with others. His Erdös number is 0 by definition. Erdös’s coauthors have Erdös number 1. There are 507 people with Erdös number 1. People other than Erdös who have written a joint paper with someone with Erdös number 1 but not with Erdös have Erdös number 2 and so on.


pages: 492 words: 149,259

Big Bang by Simon Singh


Albert Einstein, Albert Michelson, All science is either physics or stamp collecting, Andrew Wiles, anthropic principle, Arthur Eddington, Astronomia nova, Brownian motion, carbon-based life, Cepheid variable, Chance favours the prepared mind, Commentariolus, Copley Medal, cosmic abundance, cosmic microwave background, cosmological constant, cosmological principle, dark matter, Dava Sobel, Defenestration of Prague, discovery of penicillin, Dmitri Mendeleev, Edmond Halley, Edward Charles Pickering, Eratosthenes, Ernest Rutherford, Erwin Freundlich, Fellow of the Royal Society, fudge factor, Hans Lippershey, Harlow Shapley and Heber Curtis, Harvard Computers: women astronomers, Henri Poincaré, horn antenna, if you see hoof prints, think horses—not zebras, Index librorum prohibitorum, invention of the telescope, Isaac Newton, John von Neumann, Karl Jansky, Louis Daguerre, Louis Pasteur, luminiferous ether, Magellanic Cloud, Murray Gell-Mann, music of the spheres, Olbers’ paradox, On the Revolutions of the Heavenly Spheres, Paul Erdős, retrograde motion, Richard Feynman, Richard Feynman, scientific mainstream, Simon Singh, Solar eclipse in 1919, Stephen Hawking, the scientific method, Thomas Kuhn: the structure of scientific revolutions, unbiased observer, V2 rocket, Wilhelm Olbers, William of Occam

This history of cryptography involves tales of heroism and villainy, and at the same time it explains the science and mathematics behind the world’s cleverest codes. If You Loved This, You Might Like… A Beautiful Mind Sylvia Nasar Made into a Hollywood film, this is the biography of the games theorist John Forbes Nash. The Man who Loved Only Numbers Paul Hoffman Another biography of a fascinating mathematical life, namely Paul Erdös. The Victorian Internet Tom Standage The history of the telegraph, a communications revolution that puts the growth of the internet into context. Fingerprints Colin Beavan An account, as gripping as any crime novel, of how fingerprinting became central to crime detection. Can Reindeer Fly? Roger Highfield A quirky and thought-provoking examination of the science of Christmas.


pages: 405 words: 117,219

In Our Own Image: Savior or Destroyer? The History and Future of Artificial Intelligence by George Zarkadakis


3D printing, Ada Lovelace, agricultural Revolution, Airbnb, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, anthropic principle, Asperger Syndrome, autonomous vehicles, barriers to entry, battle of ideas, Berlin Wall, bioinformatics, British Empire, business process, carbon-based life, cellular automata, Claude Shannon: information theory, combinatorial explosion, complexity theory, continuous integration, Conway's Game of Life, cosmological principle, dark matter, dematerialisation, double helix, Douglas Hofstadter, Edward Snowden, epigenetics, Flash crash, Google Glasses, Gödel, Escher, Bach, income inequality, index card, industrial robot, Internet of things, invention of agriculture, invention of the steam engine, invisible hand, Isaac Newton, Jacquard loom, Jacquard loom, Jacques de Vaucanson, James Watt: steam engine, job automation, John von Neumann, Joseph-Marie Jacquard, millennium bug, natural language processing, Norbert Wiener, On the Economy of Machinery and Manufactures, packet switching, pattern recognition, Paul Erdős, post-industrial society, prediction markets, Ray Kurzweil, Rodney Brooks, Second Machine Age, self-driving car, Silicon Valley, speech recognition, stem cell, Stephen Hawking, Steven Pinker, strong AI, technological singularity, The Coming Technological Singularity, the scientific method, theory of mind, Turing complete, Turing machine, Turing test, Tyler Cowen: Great Stagnation, Vernor Vinge, Von Neumann architecture, Watson beat the top human players on Jeopardy!, Y2K

PART III: ADA IN WONDERLAND 12 All Cretans are Liars 1Aristotle’s collective writings on logic were later grouped under a book entitled Organon (which means the ‘instrument’ in Greek). 2More precisely, the title of George Boole’s book was An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities. It was the second of his two monographs on algebraic logic and was published in 1854. 3In algebra we have six operations: addition, subtraction, multiplication, division, raising to an integer power and taking roots. 4This is Euclid’s theorem, which is a fundamental statement in number theory. It was proved by several mathematicians, including Leonhard Euler and Paul Erdös. 5For example, Euclidian geometry accepts the improvable axiom that two parallel lines will never meet. 6Formally this is regarded as the fourth property of a formal logical system, and is called ‘soundness’. 7In the post-modern literary context of the twenty-first century Swift’s irony becomes a tenet: all texts can be regarded as self-produced, in that they have a transcendental-bibliographical animus which acts like a virus.


The Art of Computer Programming by Donald Ervin Knuth


Brownian motion, complexity theory, correlation coefficient, Eratosthenes, Georg Cantor, information retrieval, Isaac Newton, iterative process, John von Neumann, Louis Pasteur, mandelbrot fractal, Menlo Park, NP-complete, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, RAND corporation, random walk, sorting algorithm, Turing machine, Y2K

. | If we let k = AA(n) - 2AAA(n) in B4) for large n, where AA(n) denotes A(A(n)), we obtain the stronger asymptotic bound l(n) < l*(n) < X(n) + A(n)/AA(n) + 0(\{n)AAA(n)/AA(nJ). B5) The second term A(n)/AA(n) is essentially the best that can be obtained from B4). A much deeper analysis of lower bounds can be carried out, to show that this term A(n)/AA(n) is, in fact, essential in B5). In order to see why this is so, let us consider the following fact: Theorem E (Paul Erdos, Ada Arithmetica 6 A960), 77-81). Let e be a positive real number. The number of addition chains A1) such that A(n) = m, r < m + A — e)m/A(m) B6) is less than am, for some a < 2, for all suitably large m. (In other words, the number of addition chains so short that B6) is satisfied is substantially less than the number of values of n such that A(n) = m, when m is large.) Proof. We want to estimate the number of possible addition chains, and for this purpose our first goal is to get an improvement of Theorem A that enables us to deal more satisfactorily with nondoublings.