Summer

As a mathematician, this was a relatively eventful Summer.

It didn’t start particularly well, with the passing of

Hearing about Rudin made me sad. A friend of mine who studied at UW Madison told me that Walter and his wife Mary Ellen were like parents to the graduate students. Of course, his Analysis book (as all his textbooks, really) is greatly recommended.

I did not know Gardner was not a (formal) mathematician. He certainly did more than most to popularize the subject. I love his book of annotations on Alice in Wonderland.

[On the other hand, Izabella Laba has an interesting blog entry that (among other things) discusses what being a mathematician may mean to somebody whose only exposure to the subject comes from Gardner’s popularizing columns and similar sources.]

Arnold was a giant. As a well-known example, when he was 19, he solved (with Kolmogorov) Hilbert’s 13th problem: Any continuous function of several variables is the composition of finitely many continuous functions of two variables.

[Edit added Sept. 1/10: As I learned in Mathoverflow, it turns out that one can do even better than this: Any continuous function of two variables is the composition of finitely many continuous functions of one variable, and addition. This was originally shown by Kolmogorov, A. N. Kolmogorov, “On the representation of continuous functions of several variables by superpositions of continuous functions of one variable and addition”, Dokl. Akad. Nauk SSSR 114 (1957), 953–956; English transl., Amer. Math. Soc. Transl. (2) 28 (1963), 55–59.

Even more is true. Kahane proved the following:

Theorem. Let $\lambda$ be irrational We can ﬁnd increasing continuous functions $\varphi_j: [0, 1]\to {\mathbb R}$ for $1\le j \le5$, such that, given any continuous function $f : [0, 1]^2\to{\mathbb R}$, we can ﬁnd a continuous function $g : {\mathbb R}\to{\mathbb R}$ such that

$f (x, y) = \sum_{j=1}^{5} g(\varphi_j (x) + \lambda \varphi_j (y)).$

See these notes by T.W. Körner for details.]

Mathematics was in the news several times. I’m sure I’m forgetting examples, but we found out that:

• God’s number is 20. Rubik’s Cube was invented in 1974 by Ernő Rubik. It was licensed in 1980 and quickly became a popular puzzle worldwide. 15 years later, in 1995, Michael Reid, a mathematician at the university of Central Florida, proved that certain configurations require 20 moves to be solved. God’s number is the name given to the smallest upper bound on the number of moves required to solve the puzzle from any initial configuration. 15 years later, in July 2010, a team composed by Tomas Rokicki, a programmer from Palo Alto; Herbert Kociemba, a mathematics teacher at Darmstadt, Germany; John Dethridge, an engineer at Google in Mountain View; and Morley Davidson, a mathematician at Kent State, proved that 20 moves always suffice, so God’s number is 20. They required about 35 CPU-years of idle computer time donated by Google.
• Shigeru Kondo and Alexander Yee computed $\pi$ to $5\times 10^{12}$ digits. The computation required about 90 days, and was verified in 64 hours. The previous record was held by Fabrice Bellard, who computed $\pi$ to $2.7\times 10^{12}$ digits. In both case, a home computer was used, unlike in previous computations. For a very thorough and entertaining account of the history of computations of $\pi$, see the Life of $\pi$ talk by Jonathan Borwein. The AFP report contains this gem:

$\pi$ starts with 3.14159 in a string whose digits are believed to never repeat or end.

In August 8, Vinay Deolalikar, from HP Labs, sent an announcement to a few top mathematicians and researchers in complexity theory with a draft of a proof that P is not equal to NP. The P vs NP problem is perhaps the most famous question in mathematical logic, and is one of the 7 Millennium problems for which the Clay Mathematics Institute offers a \$1000000 dollars.

I do not know whether Deolalikar intended the proof to be made public. In any case, the manuscript was uploaded anonymously to a public website and distributed widely by email. The following week saw an unprecedented collaborative experience on the internet by many excellent mathematicians, trying to understand the draft. Consensus was quickly reached that the proof, perhaps the most serious attempt to date, was fatally flawed and far from an actual promising approach. I do not think Deolalikar expected to be put on the public eye so prominently and so quickly. As a cautionary tale, there is the following comment by Terence Tao summarizing the consensus:

To give a (somewhat artificial) analogy: as I see it now, the paper is like a lengthy blueprint for a revolutionary new car, that somehow combines a high-tech engine with an advanced fuel injection system to get 200 miles to the gallon.

The FO(LFP) objections are like a discovery of serious wiring faults in the engine, but the inventor then claims that one can easily fix this by replacing the engine with another, slightly less sophisticated engine.

The XORSAT and solution space objections are like a discovery that, according to the blueprints, the car would run just as well if the gasoline fuel was replaced with ordinary tap water. As far as I can tell, the response to this seems to be equivalent to “That objection is invalid – everyone knows that cars can’t run on water.”

The pp/ppp objection is like a discovery that the fuel is in fact being sent to a completely different component of the car than the engine.

The mathematical event of the Summer, undoubtedly, was the International Congress of Mathematicians, that ran from August 19 to 27, in Hyderabad, India. I had the opportunity to visit Hyderabad in January, for a conference, but did not attend the Congress. Fortunately, the talks were streamed live, and an archive is kept, so I could see the awards ceremony in real time, and have been listening to some of the talks at a more leisure pace.

The awards have been widely publicized, so I’ll limit myself to recall the winners, pointing to the ICM site for details (and to Tim Gowers blog for an entertaining account of the event):

• The Field medalists this time are Elon Lindenstrauss (for his use of ergodic theoretic methods in Diophantine analysis, including his partial solution of Littlewood’s conjecture), Ngô Bảo Châu (for his proof of the Fundamental Lemma in Langlands program), Stanislav Smirnov (for his work on percolation theory), and Cédric Villani (for his work on Botzmann’s equation).
• The Nevanlinna prize went to Daniel Spielman.
• The Gauss prize went to Yves Meyer.
• The Chern prize (first given this year) went to Louis Nirenberg.

The highlight of my Summer consisted of two conferences. I attended the Conference on the Core Model Induction and hod mice in Münster, and the Logic Colloquium in Paris. The conference in Münster is probably the best and certainly the most demanding I’ve ever attended; I think I was not the only one who was completely exhausted at the end of each day. You can see some pictures I took during these events, here and here.

Advertisements

2 Responses to Summer

1. jacobson12 says:

Interesting.. Especially after I first learned How to solve a Rubix Cube … Is it possible to solve in 20 moves with this method??

• (Sorry for the delay in replying, I only now saw this comment.)

As far as I know, there is not yet an “elegant” solving technique (“God’s algorithm”). However, the solution is not brute force, but builds on the “subgroup method”, as do the usual Rubik’s cube solvers one finds online or on booklets, which usually follow the example of the subgroup method due to Thistlethwaite (and require at most 52 moves).

A better example of the method is due to Kociemba, and requires at most 42 moves. This seems about right: The current (human) record for solving the cube is about 5.7 seconds, and it seems that physical limitations of the cube impose a limit of about 9 twists per second. This is probably what the CubeStormer II implements (with a record of about 5.2 seconds).

For a good description of how the algorithm that gives the optimal number builds on Kociemba’s approach, see “Twenty-two moves suffice for Rubik’s cube” by T. Rokicki, on the January 2010 issue of the Mathematical Intelligencer.