Terence Tao magic breakthrough again with EDP, Erdos Discrepancy Problem, topnotch links

1 Reply

tao_mozart➡ ⭐ ⭐ ⭐ 💡 ❗ 😮 😀 😎 hi all. Terence Tao, who is regarded as one of the greatest living mathematicians although of course not by himself (he does not even have a picture on his “about” page), has proved the Erdos Discrepancy Problem, fresh off a profile by the NYT.[a2] Tao has the distinction as being one of the very few mathematicians who has won the $3M breakthrough award, and also has said virtually nothing about it publicly (except at the awards ceremony). he’s too busy blogging about math ofc!

the EDP is a very interesting problem that relates in some sense to patterns in random walks. functions related to primes turn out to be basically very similar to “pseudo random walks”. this has been known for decades and there is a relation to the Riemann conjecture documented by Good/ Churchhouse in 1968.[g2]

the connection of hard math/ CS problems, and automated theorem proving, with analyzing random walks is a thread Ive been pursing myself over the last few years in my Collatz conjecture research. this gives me a nice moment/ opportunity/ milestone to write it all up.

its also another huge feather in the cap of the polymath project which was peripherally involved in the solution and a big triumph for cyber-collaborative mathematics.[b] a now-near-legendary almost-offhand musing in a blog comment led Tao in the right direction. “the devil is in the details…” 😈

Kalai is already casting around for the next “Big Kahuna”. any ideas? [b14] 😉 😀

this blog previously covered the Konev/ Lisitsa breakthrough using SAT theorem proving against EDP which got significant media coverage and ties in substantially with another key interest of this blog, empirical math/ (T)CS research.[h] so far Tao has not received mainstream media coverage—on this particular problem that is!—but my thinking is its merely because Stanford seems not yet to have published any press release on the preprint. its utterly fantastic this 8-decade old problem was solved, and maybe this will open/ pave the way for some other similar problems.

it is not yet well realized but (pseudo-) random walks seem to have deep unexplored connections to fractal theory.[c] have uncovered this in my own collatz research & think it is a major research area or research program.

which reminds me, have long been waiting for a moment to point this out. think ref [c8] by Walsh is actually one of the greatest unheralded discoveries in TCS if you ask me and (“small world”!) ties into my favorite problem P vs NP. p3:

Figure 4 suggests an interesting analogy with statistical mechanics. At the phase boundary in physical systems, problems tend to be “self-similar”. That is, they look similar at every length scale. At the phase boundary in computational systems, problems also display a form of self-similarity. Branching decisions give subproblems that look neither more or less constrained. This helps to explain why such problems are difficult to solve. Branching decisions tell us very little about the problem, giving subproblems that are neither more obviously soluble nor more obviously insoluble. We will often have to search to a large depth either for a solution or for a refutation.

this ref therefore talks about self-similarity in NP complete problems but without a single reference to “fractals”. virtually no other research has built on this much since then (although [c4][c5] take some stabs at it). is there some kind of stigma or blind spot there or what? do people think they only show up in nature or the stock market?

but there in a nutshell may be the explanation of hardness for P vs NP, an observation of monumental significance and which almost nobody else has remarked on much since its discovery: hard problems lead to subproblems that are self similar in a fractal way. formalizing this somehow is the massive question/ challenge that could lead to a proof. the study of computational hardness seems to be intrinsically/ inextricably/ tightly tied/ intertwined with randomness. this has been known for decades eg also with Razborov/ Rudich Natural proofs (also recently blogged on); however this insight seems difficult to exploit.

elsewhere, the Dyson conjecture seems to be related to behavior of random walks and also is loosely reminiscent of the collatz conjecture.[d]

both the Dyson & collatz conjecture relate to the behavior of base-n representations of repeated “powering”.[e] exponentiation dynamics/ complexity shows up in many deep areas of math eg RSA encryption.

also, entropy/ pseudorandomness are both loosely/ deeply connected in ways not fully appreciated.[f]

about the only article that seems to make some of these deep connections is a standout one by Wigderson, its a gem that seems to be published only on his own site. he starts out by remarking on the Riemann hypothesis and draws many other connections.[g]

there is a large area in TCS known as “derandomization of algorithms” and its another big piece of this puzzle. derandomization can be seen as a sort of decryption or extraction of algorithmic pseudorandomness. one of the biggest breakthroughs in the area was the AKS primality algorithm. other theoretical breakthroughs in TCS can be seen as derandomization applications and its connected to major open problems in the area. another significant area is with expander graphs as in this paper Entropy waves, the zig-zag graph product, and new constant-degree by Reingold, Vadhan, and Wigderson. from the abstract, shortly later used to great effect in the SL = L theorem by Reingold:

Crucial to our intuition (and simple analysis) of the properties of this graph product is the view of expanders as functions which act as “entropy wave” propagators — they transform probability distributions in which entropy is concentrated in one area to distributions where that concentration is dissipated. In these terms, the graph products affords the constructive interference of two such waves.

erdos_taocould write volumes more but am just a blogger, not a professional writer! hope that others chase down some of these connections/ leads and maybe the EDP fanfare will help increase visibility of this general area and the tricky crosscutting connections around it. am also expecting to see major mainstream media attention in the near future.

(see also earlier blog Erdös100—tribute to a brilliant contrarian)

one tiny fineprint quibble: am just as excited as or even more than everyone else—as ofc one can tell from all the emoticons—but wonder, who else in the world has actually/ really verified this extremely technical proof? it is after all a preprint… gowers seems to say its ok but did he go through it line-by-line?[b4] its surely a real life scenario replay of the old newspaper quote (difficult to trace/ attribute exactly) about einsteins theory of relativity that “only maybe a half dozen experts in the world can understand it.” its an interesting case study of the sociology of acceptance of proofs! and surely “because Tao said so” is not a definitive reason, right? must fairly note clearly/ obviously reputation is playing some role here, but thats another study for a mathematical sociologist!

a. EDP
b. polymath
c. fractal
d. dyson conjecture
e. powering
f. entropy/ randomness
g. articles/ papers
h. EDP (Konev/ Lisitsa)

1 thought on “Terence Tao magic breakthrough again with EDP, Erdos Discrepancy Problem, topnotch links”

Leave a comment