Why is Mathematics Possible: Tim Gowers’s Take on the Matter

lnc math

In a previous post I mentioned the question of why is mathematics possible. Among the interesting comments to the post, here is a comment by Tim Gowers:

“Maybe the following would be a way of rephrasing your question. We know that undecidability results don’t show that mathematics is impossible, since we are interested in a tiny fraction of mathematical statements, and in practice only in a tiny fraction of possible proofs (roughly speaking, the comprehensible ones). But why is it that these two classes match up so well? Why is it that nice mathematical statements so often have proofs that are of the kind that we are able to discover?

Continue reading

Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding  the motivation for my study. For the readers it gives an opportunity to win a $50 prize! 

Let me also bring to your attention an interesting discussion (starting here) between Peter Shor and me regarding smoothed Lindblad evolutions.

(Cris Moore, the debate’s very first comment!) I am also a little confused by Gil’s motivation for his conjectures.  (My response:)  To the best of my memory, my main motivation for skeptically studying quantum fault-tolerance was that I thought that this is a direction worth pursuing and that I had a shot at it.

micheldevoretposter (1)

While listening with Ravi Kannan to this 2002 lecture by Michel Devoret at Yale, I wondered if there are enough scientists working on the “mirage” side.

Flashback: Mittag-Leffler 2005

I started systematically thinking about quantum fault-tolerance in February 2005. There were several things that triggered my interest to the question in the previous fall and I decided to spend some time learning and thinking about it in our winter break.  One of those triggers was something Dorit Aharonov told me a few months earlier: she said that once, when she was telling her students about quantum computers, she suddenly had a feeling that maybe it was all just nonsense. Another trigger came from a former student who told me about a Polish scientist (whose name he could not remember) who wrote an article about impossibility of quantum error-correction. I thought that the lack of a quantum analog of the repetition code, and the unique properties of the majority function  in terms of sensitivity to noise that I studied with Itai Benjamini and Oded Schramm earlier could be a good starting point for looking skeptically at quantum computers.  

In our 2005 winter break, I spent two weeks at Yale and then additional two weeks at the Mittag-Leffler institute near Stockholm.  At Yale, I only had little time to think about quantum computers. I had to finish a survey article with Muli Safra about threshold phenomena (To a volume that Cris Moore and Allon Perkus were among the editors).  One of the last days in Yale we went to dinner with two guests, Chris Skinner who gave the colloquium talk, and Andrei Okounkov who visited me and gave a talk about partition enumeration and mirror symmetry. At the dinner Andrew Casson asked, out of the blue, if we think that quantum computers can be built and it almost seemed as if that Andrew was reading my mind on what I plan to work on the weeks to come. My answer there was the same as my answer now, that I tend to find it implausible.

Mittag-Leffler Institute February 2005 with Xavier Viennot and Alain Lascoux

In Sweden I spent most of my time on quantum fault-tolerance. I was jet-lagged and being jet-lagged in the Mittag-Leffler institute already worked for me once, when finding my subexponential randomized variant of the simplex algorithm was a substitute for sleeping some night in fall 1991 . In 2005 it was not as bad, I just came to my office very early in the morning and started working. And very early in the morning somebody was already playing the piano.

And who was playing the piano at the institute in the cold Swedish mornings of February 2005? The first reader to guess correctly, and convince me in a comment that she or he knows the answer without revealing it to everybody else will get $50. Continue reading

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!

Mathematics, Science, and Blogs

Michael Nielsen wrote a lovely essay entitled “Doing science online” about  mathematics, science,  and blogs. Michael’s primary example is a post over Terry Tao’s blog about the Navier-Stokes equation and he suggests blogs as a way of scaling up scientific conversation. Michael is writing a book called “The Future of Science.” He is a strong advocate of doing science in the open, and regard these changes as truly revolutionary.  (The term “Science 2.0″ is mentioned in the remarks.)

Michael’s post triggered Tim Gowers to present his thoughts about massive collaboration in mathematics, and this post is also very interesting with interesting follow-up remarks.  Tim Gowers mentioned the n-category cafe as a place where a whole research programme is advanced on a blog. Terry Tao mentioned comments on posts on his open-problems series as having some value. He  mentioned, in particular, the post on Mahler’s conjecture. (Also I think some discussions over Scott Aaronson’s blog had the nature of discussing specific technical math (coming from CS) problems.)

Tim actually proposes an experiment: trying to solve collectively a specific math problem. This would be interesting!!! I suppose we need to give such an effort over a blog a longer than ususal life-span – a few months perhaps. (And maybe not to start with a terribly difficult problem.) (What can be an appropriate control experiment though?)

Ben Webster in “Secret blogging seminar”  mentioned, in this context, earlier interesting related posts about “Working in secret“.  

Christian Elsholtz mentioned on Gowers’s blog an intermediate problem (called “Moser’s cube problem”) where you look not for combinatorial lines (where the undetermined coordinates should be 1 in x 2 in y and 3 in z), and not for an affine line (where it should be 1,2,3 in x y and z in any order), but for a line: it can be 1 in x 2 in y and 3 in z or 3 in x 2 in y and 1 in z. 

Update: Things are moving fast regarding Gowers’s massive collaboration experiment. He peoposes to study together a new approach to the k=3 “density Hales -Jewett theorem”. A background post apears here. Hillel Furstenberg and Izzy Katznelson’s proof of the density Hales-Jewett theorem was a crowning achievement of the ergodic theory method towards Szemeredi’s theorem. Like the case for Furstenberg’s proof of Szemeredi’s theorem itself the case k=3 was considerably simpler and had appeared in an earlier paper by Hillel and Izzy. The recent extensions of Szemeredi regularity lemma that led to simpler combinatorial proof of Szemeredi’s theorem did not led so far to simpler proofs for the density Hales-Jewett case. If you look at Tim’s background post let me ask you this: What is the case k=2 of the density Hales-Jewett’s theorem? It is something familiar that we talked about! 

Here is a particularly silly problem that I suggested at some point along the discussions: How large can a family of subsets of an n-element set be without having two sets A and B such that the number of elements in A but not in B is twice the number of elements in B but not in A?

Update: This problem was completely reolved by Imre Leader and Eoin Long, their paper Tilted Sperner families contains also related results and conjectures.

Massive collaboration in art (click the picture for details)

Q: What is the case k=2of the density Hales-Jewett’s theorem? A: It is  Sperner’s theorem! (that we discussed in this post.)

I will keep updating about news from Tim’s project. [Last update is from October 21].  More updates: Tim’s project is getting quickly off the ground. A useful wiki was established. More update: It is probably successful

Continue reading