Erdös100—tribute to a brilliant contrarian

hi all! this week is Erdös’ 100 birthday. thought I would celebrate by writing a blog tribute. there are lots of other recognitions and anecdotes on other mathematics and complexity theory blogs and lots of good fresh links on it. eg sci am[1], simons foundation[3], even cyber MSM coverage by huffingtonpost![2] surprising! he must really have been famous. [3] has a nice short video synopsis.

yeah Erdös was a sort of 20th century mathematical einstein and the two had some similarities in character. contrarian, eccentric, nonconformist. both liked to travel. both seemed to revel in their widespread public recognition.

Erdös is sort of like an itinerant mathematical monk. he had a zen buddhist feel to his personality and also his mathematics. he was a mathematical philosopher—with equations for words.

he abstained from personal possessions. he was in many ways intensely antimaterialistic in an intensely materialistic age. he seemed like a foreigner or visitor in our land, except that it was at times so extreme he seemed like a foreigner on planet earth!

it is said that Erdös was not a great visionary type, shying away from bold and sprawling problems or research programs, but he did lots of incremental work, some of it quite brilliant.

but I would question this. he had a fervent, fanatic interest in great mathematics, and great mathematics will always live on. he seemed to have incredible intuition for areas that would later become very significant, eg graph theory. when he started working in this area, it had a very theoretical flavor, such that only research mathematicians would be interested. even graph theory itself was looked down on somewhat at the time of its flowering in the 1960s. this was pointed out in a recent interview by Lovasz on the simons web site.[19]

its sometimes hard to realize, working in a scientific area, that only a few decades ago it was relatively nonexistent, as the colorful expression goes, just a “glimmer in others eyes”.

Erdös’ idea to work on the theory of random graphs was quite radical at the time, and revolutionary in its implications. random graph theory is now seen to be a theory with a vast, highly applied area of application. what changed? our modern age of ubiquitous networking has something to do with this, but in many ways it was a revolution in our scientific worldview. the world is not so much different but our view of it is now.

Erdös was the ultimate collaborator, of now superlatively legendary proportions.[8] one wonders how he would have adopted his style to the modern form of email, electronic preprints, web sites, blogs, social networking, chat. would he have embraced the highly social aspects of the internet, or shunned its technological edge? in our time science research itself also seems to be becoming more inherently collaborative and interdisciplinary. in some ways the internet would be a dream come true for his style. I also have long dreamed of mathematical collaborations. nobody will probably ever achieve the level of collaboration of what Erdös did in his lifetime.

Erdös also did not seem to be interested in experimental or empirical mathematics at all, which in my opinion is starting to really flower and blossom in our time with the computer revolution [now showing up on a tablet or smartphone near you]. intend to write up a large blog post on that at some point [have a bazillion links already]. in this he reminds me a little of Ray Bradbury who died somewhat recently– a strange mix of the futuristic and backward (or lets just say “verging on curmudgeonly in select areas”).

I read the great biography “the man who loved only numbers” shortly after it was published.[4][13][14][15] I really identify with Erdös love of mathematics and minimal personal human relationships. he had close personal friends but it appears, no family. a strange combination.

in my own research on complexity theory, Erdös’ trailblazing stands out. it appears the theory of random graphs and transition points[10] is highly relevant to the P vs NP question in multiple unexpected and surprising, sometimes startling ways. it seems to be intrinsic to the mathematical theory of “bottlenecks” which is now in its infancy or even embryonic stage but definitely seems like it might/will grow.

the theory of sunflowers seems to show up in key complexity theory problems.[5][7] its in a brand new paper by Alon et al called “on sunflowers and matrix multiplication”.[18]

there is a 1993 film profile on Erdös, N is a Number.[17] am thinking Ive gotta watch it soon. its available over the internet. yay![6]

* * *

I think I first heard about Erdös from a mathematician-wannabe teacher at my high school, TB, in the late 1980s. “TB” was an extraordinary teacher although I didnt realize it at the time and I should share some anecdotes about him someday out of a tribute to him also. TB read exhaustively and had an incredible grasp of math history, possibly where I picked up some of my own affinity for it.

TB told me about Erdös once, as the wandering mathematical monk who had no possessions, was unaffiliated with any university or job, and only worked on math papers, and his story was so weird & outlandish I found it hard to believe at first! but, somehow, secretly entranced and enthralled at the concept! he was sort of the equivalent of a mathematical surf bum! who was somehow so contrarian he even avoided most of the overall social Matrix which all the rest of us mere mortals swim in! in this way Erdös was very much like a modern version of those old Greek philosophers who seemed to eschew reality itself, a sort of modern day Pythagoras…

years ago in my younger days I had fantasies of getting a remote/secluded island or mountain hideaway, and work on software and mathematics theorems. possibly influenced by a few whiffs of the the Erdös zeitgeist!

Ive worked hard on a problem that Erdös apparently shunned out of aversion to perceived/estimated difficulty, the Collatz conjecture.[9] he didnt seem to have said anything at all about this deep problem in number theory which one might think is perfectly suited for his style. except!

“Mathematics is not yet ripe for such problems.”

in this way Erdös was a living embodiment and epitome of that old aphorism, “choose your battles wisely.” very wise and sage advice in the area of theory and mathematics.

yes, Erdös was very aware of mathematical research progression and evolution. he didnt seem to like to work in highly refined areas of mathematics with large cathedral-like structures/edifices. he was more into a mathematical “bazaar” type mentality.[20] (one suspects he might have supported some of the new ideas about open science publishing because it was much in line with his background.)

[12] is a list from 1993 of Erdös open problems with awards attached, posted to Usenet. [does anyone remember that? hoo-eee feel like a gray-headed oldtimer.] by Greg Kuperberg, now the 2nd-highest rep mathoverflow celebrity[22], an extraordinary cyber feat. [mathoverflow has some very elite mathematicians who run up their scores, in contrast to the much more reserved cstheory stackexchange where very few of the fields elite literati hang out regularly.] [15] is another more recent list of problems but without any prizes listed.

Erdös had a great facetious attitude about his prizes. the work required versus the monetary payoff is incredibly, absurdly asymmetrical. there are problems on the list that wont be solved for decades, probably. but math also has this weird property that some may seem to be seen as trivial in decades hence. in this way math has a little bit in common with marching technological onslaught [eg with Moores law etc].

I wonder what Erdös would have thought of the $7M Clay Math prizes. the prize aspect would have surely intrigued him, but the large [materialistic!] prize might have been somehow unattractive for him.

speaking of mathoverflow, and maybe a little in celebration of Erdös birthday I coincidentally/synchronicitously posted a new question to mathoverflow relating to cliques on random graphs which I believe is at the heart of a P vs NP proof.[16] it truly amazes me how such simple questions require so much deep analysis to answer or similar questions may be unanswerable within current theory.

mathematics is truly extraordinary how simple-to-state questions can have massive ramifications toward their solutions, an asymmetry that seemed to fascinate Erdös, who in his contests gave *exclusively* simple problem statements! again his zen quality. it appears that mathematics itself is a different kind of zen. maybe in some ways the most intense zen of all!

this is also known as “hidden depths”, as with icebergs.[24] number theory seems to be enmeshed with, to the point of even uniquely epitomizing, this astonishing principle/phenomenon. the legendary example of this is Fermats Last Theorem which took 3.5 centuries to resolve! another new example may be the ABC conjecture where a recent rumored proof by Mochizuki circulating amounts to *hundreds of pages* over several papers.[25],[26]

[23] is one of the highest-voted cstheory stackexchange questions (currently 188 votes) with an Erdös-inspired flavor/angle, asking for “algorithms from the Book”.

recently on cstheory stackexchange there was a question by Lev Reyzin celebrating Turings 100 yr anniversary by asking about his contributions.[11] there certainly deserves to be an identical one on Erdös. however, didnt ask it myself, because unlike self-abnegating Erdös, I care only about earning reputation points on these sites, haha. (or maybe, need to have more offline scientific credibility like Lev Reyzin does to get away with asking questions like that!) or maybe am afraid of all the people on there who constantly, endlessly criticize my ee.cummings cyber style![21] what can I say, am a little contrarian, eccentric, and nonconformist myself!

other links: [27], on a new childrens book called “The boy who loved math” with a Erdös-inspired puzzle, and [28], Erdös centennial conference in Budapest in July. [29] wikipedia entry. [30], online searchable site of papers, many online.

• [1] An Arbitrary Number of Years Since Mathematician Paul Erdös’s Birth: Scientific American
• [2] Colm Mulcahy: Centenary of Mathematician Paul Erdös– Source of Bacon Number Concept
• [3] N is a Number: A Portrait of Paul Erdös | Simons Foundation
• [4] Amazon.com: The Man Who Loved Only Numbers: Paul Hoffman: Books
• [5] co.combinatorics – Detailed Materials on Sunflowers – Theoretical Computer Science
• [6] N is a Number: A Portrait of Paul Erdös – FORA.tv
• [7] CiteSeerX — The Monotone Complexity of k-Clique on Random Graphs
• [8] Erdös Number Project – The Erdös Number Project – Oakland University
• [9] Collatz conjecture – Wikipedia, the free encyclopedia
• [10] ds.algorithms – How to generate graphs with known optimal vertex cover – Theoretical Computer Science
• [11] soft question – Alan Turing's Contributions to Computer Science – Theoretical Computer Science
• [12] http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd
• [13] The Man Who Loved Only Numbers, NYT book except
• [14] Planning an Infinite Stay, NYT book review
• [15] Does there exist a comprehensive compilation of Erdös's open problems? – MathOverflow
• [16] counting k-cliques not also (k+1) on random graphs – MathOverflow
• [17] ZALA films: N is a Number
• [18] On Sunflowers and Matrix Multiplication Alon, Shpilka, Umans
• [19] Laszlo Lovasz interviewed by Noga Alon
• [20] Cathedral and the Bazaar by Raymond
• [21] ee cummings
• [22] greg kuperberg, mathoverflow
• [23] algorithms from the book
• [24] hidden depths poster
• [25] mochizuki ABC proof, polymath survey
• [26] what are the implications of the ABC conjecture in TCS? cstheory stackexchange
• [27] The Improbable Life of Paul Erdős
• [28] Erdős Centennial Budapest, Hungary, July 1-5, 2013
• [29] Erdös, wikipedia
• [30] collected papers of Paul Erdös online, searchable