Why is mathematics possible?

Spectacular advances in number theory

Last weeks we heard about two spectacular results in number theory.  As announced in Nature, Yitang Zhang proved that there are infinitely many pairs of consecutive primes (p_n, p_{n+1}) which are at most 70 million apart! This is a sensational achievement. Pushing 70 million to 2 will settle the ancient conjecture on twin primes, but this is already an extremely amazing breakthrough.  An earlier breakthrough came in 2005 when Daniel Goldston, János Pintz, and Cem Yıldırım proved that the gaps between consecutive primes p_{n+1}-p_n is infinitely often smaller than \sqrt {\log p_n} \log \log ^2 p_n.

Update: A description of Zhang’s work and a link to the paper can be found on Emmanuel Kowalski’s bloog Further update: A description of Zhang’s work and related questions and results can be found now in Terry Tao’s blog. Terry Tao also proposed a new polymath project aimed to reading Zhang’s paper and attempting to improve the bounds.

Harald Helfgott proved that every integer is the sum of three primes.  Here the story starts with Vinogradov who proved it for sufficiently large integers, but pushing down what “sufficiently large” is, and pushing up the computerized methods needed to take care of “small” integers required much work and ingenuity.

Why is Mathematics possible?

The recent news, and a little exchange of views I had with Boaz Barak, bring us back to the question: “Why is mathematics possible?” This is an old question that David Kazhdan outlined in a lovely 1999 essay “Reflection on the development of mathematics in the twentieth century.” The point (from modern view) is this: We know that mathematical statements can, in general, be undecidable.  We also know that a proof for a short mathematical statement can be extremely long. And we also know that even if a mathematical statement admits a short proof, finding such a proof can be computationally intractable. Given all that, what are the reasons that mathematics is at all possible?

It is popular to associate “human creativity” with an answer. The problem with incorrect (or, at least, incomplete) answers is that they often represent missed opportunities for better answers. I think that for the question “why is mathematics possible” there are opportunities (even using computational complexity thinking) to offer better answers.

Please offer your answers.

Dan Mostow on Haaretz and Other Updates

Enlightenment at a red traffic light

Wolf Prize laureate Prof. George Daniel Mostow made his greatest scientific breakthrough while driving.

Haaretz tells the story of how Dan Mostow reached his breakthrough known as Mostow’s rigidity theorem.

Mostow

Congratulations, Dan!

French-Isreali Meeting and Günterfest

French-Isreali

More updates: If you are in Paris On Wednesday and Thursday this week there will be a lovely French-Isreali interacademic meeting on mathematics.  The problem is very interesting, and I will give a talk quite similar to my recent MIT talk on quantum computers.

In the  weekend  we will celebrate Günter Ziegler’s 50th birthday in Berlin. Günter started very very young so we had to wait long for this.

ziegler

 Happy birthday, Gunter

Meeting with Aram Harrow, and my Lecture on Why Quantum Computers Cannot Work.

Last Friday, I gave a lecture at the quantum information seminar at MIT entitled “Why quantum computers cannot work and how.” It was a nice event with lovely participation during the talk, and a continued discussion after it. Many very interesting and useful remarks were made. Here are the slides. (The abstract can be found on this page.)

After having an almost a year-long debate with Aram Harrow, I finally met Aram in person, and we had nice time together during my visit.

AramGil

Aram is so nice that had it been up to me I would certainly make quantum computers possible :) (But this is not up to us and all we can do is to try to explore if QC are possible or not.)

We talked about quite a few topics starting with various exotic models of noise that treat differently classic and quantum information, the relevance of locally correctable codes and their quantum counterparts, the sum of Squares/Lasserre hierarchy, unique games and hypercontractivity, my smoothed Lindblad evolutions , NMR and spin-echo, quantum annealing and stoquasicity, and works by Mossbüer, Rekha Thomas, and Monique Laurent were mentioned. 

More

I just returned yesterday night from Yale after a very fruitful visit.  Here is a picture of a snowcar decorated with car mirrors from the great blizzard.

winter12 224

Election Day

Vox populi, vox dei!

Today is the general election day in Israel. This is an exciting day. For me election is about participation much more than it is about influence and I try not to miss it.  This is why I regard the influence-based arguments for “why it is irrational to vote,” as unconvincing, and even a little silly. Influence vs participation was also the basis for my poll on “would you decide the election if you could.” I voted ‘no’ but about two-thirds of the participants voted yes. Four years ago I brought on this day the nice story of Achnai’s oven.

Postoctoral Positions Available

Positions_Available

Maybe I should say that (like every year but even more so) we do have funding for 1-2 postdoctoral positions in combinatorics, for 1-3 years starting in the next academic year (the time is flexible) here at the Hebrew University of Jerusalem. If you do research in combinatorics or in related areas you may enjoy our special environment (and weather, and sights), our lovely group of combinatorialists both in the mathematics and the computer science departments, and the other great reseach groups around. (We can supply recommendations from people who enjoyed it here and had a fruitful time.)

We can also support short term visits of graduate students and postdocs.

If you are interested, especially if you are (more or less) interested in the type of things I am doing – please send me an email. (Maybe write in the subject: “postdoctoral position in combinatorics”.)

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus?

Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my scientific debate with Aram Harrow regarding quantum fault tolerance is essentially over. Some good food for thought, I hope. As always, there is more to be said on the matter itself, on the debate, and on other”meta” matters, but it is also useful to put it now in the background for a while, to continue to think about quantum fault tolerance in the slow pace and solitude, as I am used to, and also to move on in other fronts, which were perhaps neglected a little.

Here are the links to the eight posts: My initial post “Perpetual Motion of The 21st Century?” was followed by three posts by Aram. The first “Flying Machines of the 21st Century?” the second “Nature does not conspire” and the third “The Quantum super-PAC.” We had then two additional posts “Quantum refutations and reproofs” and “Can you hear the shape of a quantum computer?.” Finally we had  two conclusion posts: “Quantum repetition” and “Quantum supremacy or quantum control?

EDP 22-27

We had six new posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought.  Other participants also contributed a few comments. One nice surprise for me was that the behavior of the hereditary discrepancy for homogeneous arithmetic progression in {1,2,…,n} was  found by Alexander Nikolov and  Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is {\tilde{\Omega}(\sqrt{\log n})} and at most {n^{O(\frac{1}{\log\log n})}}, and to my surprise Alexander and Kunal showed that the upper bound is the correct behavior. The argument relies on connection with differential privacy.

Möbius randomness and computation

After the AC^0-prime number theorem was proved by Ben Green, and the Mobius randomness of all Walsh functions and monotone Boolean function was proved by Jean Bourgain, (See this MO question for details) the next logical step are low degree polynomials over Z/2Z . (The Walsh functions are degree 1 polynomials.) The simplest case offered to me by Bourgain is the case of the Rudin-Shapiro sequence. (But for an ACC(2) result via Razborov-Smolensky theorem we will need to go all the way to polynomial of degree polylog.) I asked it over MathOverflaw. After three months of no activity I offered a bounty of 300 of my own MO-reputations. Subsequently, Terry Tao and Ben Green discussed some avenues and eventually Tao solved the problem (and earned the 300 reputation points). Here is a very recent post on Möbius randomness on Terry Tao’s blog.

Influences on large sets

In my post Nati’s Influence I mentioned two old conjectures (Conjecture 1 dues to Benny Chor and Conjecture 2) about influence of large sets on Boolean functions. During Jeff Kahn’s visit to Israel we managed to disprove them both. The disproof is inspired by an old construction of Ajtai and Linial.

Tel Aviv, New Haven, Jerusalem

Last year we lived for a year in Tel Aviv which was a wonderful experience: especially walking on the beach every day and feeling the different atmosphere of the city. It is so different from my Jerusalem and still the people speak fluent Hebrew. I am now in New Haven. It is getting cold and the fall colors are getting beautiful. And it also feels at home after all these years. And next week I return to my difficult and beautiful  (and beloved) Jerusalem.

Some Updates

Jeff Kahn was in town: so we worked together also with Ehud Friedgut and Roy Meshulam (and others) quite intensively. Very nice! Stay tuned for a report!

Polynomial Hirsch conjecture (polymath3): While the conjecture remains wide open there are some interesting developments. The conjecture asserts that the diameter of every d-dimensional polytope with n facets is at most polynomial in d and n. Jesus de Loera and Steve Klee described simplicial polytopes which are not  weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about \sqrt{d} was proved  by Hähnle, Klee, and Pilaud in the paper  Obstructions to weak decomposability for simplicial polytopes. Karim Adiprasito and Bruno Benedetti proved the Hirsch conjecture for flag polytopes (and manifolds) using CAT(0) methods. Karim will write a guest blog post about it. Stay tuned.

Erdos discrepancy problem (polymath5): Tim Gowers and I have a plan to try soon to revive the EDP project at least for a short while. We plan 3 posts about it in the second half of August over Tim’s blog. Update: The first post EDP22 just appeared.

Polymath7 is going strong on the polymath blog.

Quantum computer debate with Aram Harrow: The most recent post was entitled Can you hear the shape of a quantum computer? Quite an interesting discussion, also on the Quantum pontiff.

“Gold open access” new Forum: See the post and extensive discussion over Gowers’s blog (and also on Tao’s blog).

Telling spheres: Joel Hass was in town and gave a talk about a recent work with Greg Kuperberg: Telling if a 3-manifolds  is a sphere is in co-NP (assuming GRH). This extends Greg’s work on telling unknots. Topology, provides remarkable questions in NP and coNP where proving both sides are hard. My claim to fame is replacing Joel in grading an exam in 1986 (or so) when he got married!

High dimensional expander. My course with Alex Lubotzky on high dimensional expanders ended. A lot of nice things to tell about and we learned quite a few new things. Roy Meshulam concluded his course with a crystal clear lecture on Garland’s method. Maybe we will teach it again after a year break. Meanwhile, Ori Parzanchevski promised me to write something about some recent developments over here. Stay tuned for that too.

16th Midrasha Mathematicae: Our yearly midrasha ran by Aner Shalev was devoted to Words and Growth. Delicious approximate groups and word maps were observed!

Interactive quantum lecture: We had an unususal quantum seminar presentation by Michael Ben-Or on the work A multi-prover interactive proof for NEXP sound against entangled provers by Tsuyoshi Ito and Thomas Vidick. Michael ran Vidick’s videotaped recent talk on the matter and from time to time he and Dorit acted as a pair of prover and the other audience as verifier. (Michael was one of the authors of the very first paper introducing multi-prover interactive proofs.)

Peter Frankl: I plan on meeting Peter on Friday. Will report.

Knighted for Services to Mathematics

The Birthday and Diamond Jubilee Honours 2012 was released on 16 June 2012 in the United Kingdom and Tim Gowers was knighted for “services to mathematics”! So I suppose Tim is now becoming “Sir William.”

It is possible that the Queen mainly thought about Tim’s wonderful research contributions. (Indeed, I was told, lately she took the relevant volumes of GAFA with her to bed.) But certainly Gowers’s services to mathematics include also the Princeton companion and the very short introduction, general-public presentations, Gower’s blog and Tim’s frequent

comments on other blogs, Polymath, Contributions to MathOverflow (the first user to get eight golden badges, among other things), Fighting Elsevier (which is now referred to as the “academic spring“) and more. Congratulations!