Aspen Blog

This blog is meant to provide a poor substitute for the first three lectures of Physics 7653. I'm attending an Aspen workshop with the title Disorder, Algorithms and Complexity that I committed to over a year ago, before the actual dates had been set. If everything goes as planned I will be giving lectures in-the-flesh starting September 4. In the meantime, I will try to conduct the class remotely via this blog. I thought about uploading lectures for you to read and then decided that would take most of the fun out of them. So instead, you will get a mixture of items of a more diverse nature with the hope that it will stimulate your interest in statistical physics. To set the stage, the photo above on the left shows your interpid physics blogger (red hat) attempting to photograph a small bear on the grounds of the Aspen Center for Physics.

The photo on the right is your first homework assignment. For full credit, identify what it is and email your answer to me.

The USA Pro Cycling Challenge visits Aspen while you take on the Pro Statistical Mechanics Challenge

Aspen has been taken over these past two days by a major cycling competition, the USA Pro Challenge, a kind of Tour-de-Colorado. Most of the roads in this mountain town, including the only egress to the East, 12,095' Independence Pass, were closed for several hours. Above is a photo I took of legendary cyclist and "domestique" of Lance Armstrong, George Hincapie, who is retiring this year.

I cannot stress enough the importance of challenging yourself with original problems, especially if you are thinking of pursuing a career in theoretical physics. You will be judged not only by the hard problems you have solved, but by the coolness of the problems you've posed (irrespective of having solved them yourself). I have therefore chosen as your second homework assignment a beautiful problem first asked (and also solved) by former Cornell physics grad Eric Cockayne. This problem is quite challenging and you shouldn't despair if you don't get it right away. I'll provide hints, based on class progress.

Okay, here it is: $$N$$ points are placed at random on the surface of a sphere in $$D$$ dimensions. Calculate the probability, $$P_D(N)$$, that all $$N$$ points lie in the same hemisphere.

This is a very simple example of a phase transition. The probability switches from 1 to 0 as the number of points $$N$$ is increased, and the switching becomes increasingly abrupt in the "thermodynamic limit" of large $$D$$. You might ask how can this be like a physical phase transition, since there are no interactions that could generate cooperative behavior -- after all, the $$N$$ points are chosen independently at random. The short answer to this excellent question is that in this case the phase transition arises from the nature of the property that is being considered (all points within the same hemisphere). Phase transitions of this type are increasingly attracting the attention of statistical physicists.

A famous example, so far only partially understood and a subject of debate at the Aspen Workshop, is the problem of random Boolean formulas. Even when the elements of the formula are chosen independently at random, there is a phase transition from the formula being "satisfiable" (evaluates to TRUE for some choice of TRUE/FALSE assignment to the variables) to being "unsatisfiable" (no assignment makes the formula TRUE). This "SAT/UNSAT transition" happens as a function of the length of the formula, measured in terms of the number of clauses.

Eric's problem is much easier than SAT/UNSAT. I will make just a few remarks today to get you started. The first incredibly huge hint is that with a bit of insight the calculation of the probability reduces to a counting problem. If you are setting up integrals you are on the wrong track! The second thing I'll mention is that it really helps to first completely analyze the cases $$D=1$$ and $$D=2$$. If you think you found the formula for $$D=2$$ send it to me by email as a kind of progress report and we'll continue from there.

Truth islands as pure states

I ride one of the Center's mountain bikes up to Maroon Lake (9,580') every morning, usually rewarded by a dramatic view of the Maroon Bells (14,156' and 14,014'). However, today a thick fog filled the valley with the result shown in the photo above. The hard work of climbing out of Aspen always goes faster when I think of a physics or math problem. There was a colloquium here yesterday by Dan Stein about spin glasses, where he often referred to "pure states". While I understand what this term means in the context of quantum mechanics, at the talk I was very confused how that could extend to classical statistical mechanics (spin glasses).

It wasn't until Sue Coppersmith, a workshop organizer and very sharp (and funny) former Cornell physics grad, explained it to me that the fog lifted. Before I get into that I might mention that this workshop has a strong Cornell connection. Two of Sue's co-organizers are Cris Moore, a former student of Jim Sethna's, and Ben Machta's father, Jon. I highly recommend the textbook Cris co-authored with Stephan Mertens. Finally, Bart Selman from the Cornell CS department is here. When Bart was at Bell Labs he made the discovery that random Boolean formulas exhibit a satisfiability phase transition (see yesterday's entry).

An Ising ferromagnet below the ordering transition has two pure states. Think of the joint probability distribution of all the spins. It's defined on a hypercube of very large dimension. In one pure state the distribution is strongly concentrated near the "all up" vertex and diminishes rapidly with the number of steps (spin flips) away from that vertex. The other pure state is concentrated at the "all down" vertex. The overlap of the two pure state distributions is very small, decaying exponentially with the size of the system. For a physicist the construction of a "mixed state", defined by a normalized combination of the two pure state distributions, seems like a perversity but it is technically a valid thermodynamic equilibrium state (in the absence of a magnetic field).

Spin glasses are believed to have a very large number of pure states, not just two. And there is nothing obvious, like an applied field, that allows you to select particular ones. The same state of affairs is believed to apply to the distribution of Boolean variables that make a large random formula evaluate to TRUE, when the parameters that describe the structure of the formula (clause/variable ratio) are in a certain range. Imagine a "truth distribution" comprising a huge number of isolated islands surrounded by a sea of zero probability. Within each island you can make a small number of steps on the hypercube (flip a few variables) and still have the formula evaluate to TRUE. On the other hand, island hopping, which also preserves the truth of the formula, requires that a finite fraction of the variables be flipped. In a sense, each of these truth islands is novel and exotic because of the location it occupies in the sea.

There is a class of algorithms, called "local search", that run into problems when there is a proliferation of truth islands. These algorithms start in the sea and flip one variable at a time, all the time trying to make the formula a little more true (measured in terms of the number of true clauses). The problem arises when one part of the formula responds to the presence of one nearby island, while another part of the formula responds to the presence of another island. The result is that the algorithm finds neither island and makes no progress.

Riding through the fog up to the Maroon Bells this morning I had the thought that an algorithm that makes long moves in each step, that are still "smart" in some sense, will have an advantage over local search in the difficult spin glass regime. Earlier this week I described the difference map algorithm in the outdoor seminar room; you can see me making a long move in the photo below. This algorithm is often lumped together with other local search algorithms, a perception that I should try to correct. The moves are long, typically updating a finite fraction of all the variables in each iteration. But whether the long moves are sufficiently smart to actually improve the chances of landing on an island is still unclear. Perhaps tomorrow there will be a break in the fog.

Daniel Fisher (Cornell alumnus) solves the disk packing challenge

So far I have not received many progress reports on the Pro Statistical Mechanics Challenge (Eric Cockayne's problem). In fact, none at all! Do I have to post a picture of the amazing probability distribution to get you excited?

The probability that $$N$$ randomly placed points lie within the same $$D$$-dimensional hemisphere, for $$D=10,100,1000$$.

I promise you when you solve this challenge your sense of triumph will not be unlike Daniel Fisher's, when he dropped in that last disk in the packing challenge. You will get another huge hint tomorrow. Until then, please do two things: (1) work out the case $$P_1(N)$$ and (2) show that $$P_D(D)=1$$.

One giant leap for mankind?

I was delighted to receive answers to both of the homework problems in the last 24 hours. The first one is an example of the SCAT transition, not to be confused with SAT. Several of you commented on my bravery in capturing the bear at such close range, even if, for purely aesthetic reasons, it does not rise to the level of National Geographic.

Workshop participant Michael Biehl pointed out that Eric Cockayne's problem has a long history, going back at least as far as Ludwig Schlaefli, the Swiss mathematician. For those of you who emailed solutions for $$P_1(N)$$ and $$P_2(N)$$, and proofs of $$P_D(N)$$=1 for $$N\le D$$, I very much appreciate your clear and careful reasoning. As promised, here's the really powerful hint for doing the general case, if you need it:

Let's sample $$N$$ random points on a sphere in the following strange way. This works for any $$D$$, but I suggest you make sketches (mentally or on paper) for either $$D=2$$ or $$D=3$$. Rather than points, choose $$N$$ random diameters that join opposite pairs of points. Then, for each choice of diameters there are $$2^N$$ ways of choosing their endpoints to get a sample of points. So consider the following subproblem: The $$N$$ diameters have been chosen; what is the probability $$P'_D(N)$$ that an endpoint configuration, on those diameters, has the property that all points lie in the same hemisphere? And here's the amazing fact: $$P'_D(N)$$ doesn't depend on the choice of diameters at all (aside from exceptional cases which have zero measure) and is therefore equal to the probability $$P_D(N)$$ we are after!

I fight back exhaustion and boredom to arrive at Independence Pass

I wouldn't have done what I did this morning if it weren't for my Cornell colleagues, Vinay Ambegaokar and Paul Ginsparg, who did the very same thing at various times in the past. The winding road from Aspen to Independence pass climbs 4200' over 19 miles: roughly the equivalent of riding 20 times up Buffalo. Sure it's hard, but what people forget is the very long time you are sitting on bike no. 4, about 2 3/4 hours in my case. How does the human nervous system handle boredom at high elevations? In my case it was a kind of random "cycling" between (1) cursing individual components of the Riemann tensor (there are a lot of them), (2) mumbling inspirational phrases somebody had spray painted on the road ("Feared by many, even Chuck Norris"), and (3) thankfully, the chacone movement of Bach's solo violin partita no. 2.

The Bach chacone reminds me of a wonderful side benefit of these summers at the Aspen Center: the Aspen Music Festival and School. The festival runs 8 weeks and many of the concerts take place inside a giant tent right next to the Physics Center (we had no trouble hearing them rehearse Mahler's 8th). The music school attracts students at a very high level, and in addition to formal concerts they give recitals at various venues, including the Physics Center. My son Toby was so taken by a recital of the Bach chacone he sight-read the whole thing as soon as we got back to our Aspen apartment!

To give you an idea how amazing this piece of music is, here's a story from my graduate student days. I had heard it on the radio and then did what people did in those days: bought an LP recording of it at the local record store. On the cover was the picture of a well known virtuoso so I knew the quality would be high. Back in my Berkeley apartment, after putting the LP on the turntable, I flipped to the back of the album to find out who the other violinists were! That's right: this piece is so complex that your first impression is that it's being performed by a duo or trio.

View from the Aspen Center for Physics: music tent (behind aspen trees) and red mountain

Having just taken my final ride up to the Maroon Bells I'm retiring bike no. 4 and thinking of all the preparaions for the (car) ride back to Ithaca. Because internet access along the way is not guaranteed, this will have to be your final installment on the Cockayne-Schlaefli problem. I really hope you can wrap this up before the first lecture next Tuesday!

Okay, if you worked through the last hint you should have come to the conclusion that this problem is all about counting a geometrical set. There are lines ($$D=2$$), planes ($$D=3$$), or hyperplanes ($$D\gt 3$$) perpendicular to the random diameters described previously. These divide up the $$D$$-sphere into regions called "chambers". Each chamber represents one of the possible ways to choose diameter endpoints so they all lie on a common hemisphere. When you pass from one chamber to an adjacent one, by crossing one of the hyperplanes, the endpoint on the corresponding diameter has to be switched. Let $$C_D(N)$$ be the number of chambers created by $$N$$ hyperplanes in $$D$$-dimensions. In $$D=2$$ it's easy to see that this number does not depend on how the diameters are arranged. But it's true in general, and a nice way to see it is to write down a recursion relation for the chamber numbers from which the invariance follows by induction.

There's a simple linear relation between $$C_D(N+1)$$, $$C_D(N)$$ and $$C_{D-1}(N)$$. You can derive it by working out how the count increases when you add one more hyerplane to a configuration of $$N$$. The chamber number recursion is easily solved if you arrange the numbers in the obvious square table (axes $$D$$ and $$N$$) and draw arrows to represent how the table entries feed into one another. The most convenient way to start the recursion is from the values $$C_D(1)$$=2 for $$D\ge 1$$, and $$C_D(1)$$=0 for $$D\lt 1$$. You are probably wondering how I came up with the value zero for chamber numbers in zero and negative dimensions! The explanation is that for this choice and the recursion relation you will derive, it follows that $$C_1(N)$$=2, a valid result. So rather than use both axes of the table to start the recursion (from non-zero $$D$$ and $$N$$) I suggest using just the infinite row $$N=1$$ with zero values for $$D\lt 1$$.

With the last hint you should have no trouble writing down an explicit formula for $$P_D(N)$$ having the form of a sum over binomial coefficients, a discrete analog of the error function. Apply Stirling's approximation for the large $$D, N$$ limit to obtain (1) the value of $$N/D$$ where the probability makes its transition from 1 to 0, and (2) the scaling of the width of the transition region. Good luck!

You can think of the Cockayne-Schlaefli problem as a simpler analog of the random Boolean satisiability problem. In the latter we are interested in finding the SAT/UNSAT transition, as the number of logical clauses is increased relative to the number of variables. Cockayne-Schlaefli corresponds to the linear programming feasibility problem which asks whether the system of inequalities $$A\cdot x\gt 0$$ has a solution for the vector $$x$$. Here $$A$$ is an $$N\times D$$ matrix of numbers drawn from a Gaussian distribution. The rows of $$A$$, after normalizing to unit length, correspond to the points on the $$D$$-sphere, and the vector $$x$$, if it exists, defines the hemisphere that contains all the points. The function $$P_D(N)$$ therefore represents the probability that random linear programs (of a particular type) have solutions (a feasible point). The analog of $$P_D(N)$$ for Boolean satisfiability is not known. The state of the art is reviewed in Donald Knuth's recently released Pre-fascicle 6a of the Art of Computer Programming. You can find a plot of the satisfiability probability for 5 Boolean variables as a function of the number of clauses (each with three variables) on page 2.

I will now do something that has never been done before and so you are a witness to a singular event: I'm going to terminate this blog! Before the final upload I need to add two items. First, I promised the workshop participants a movie showing the difference map algorithm solving the disk packing challenge:

Difference map solution of the disk packing challenge

Finally, I want to remember my hero Bill Thurston who sadly passed away last week. There is a theorem due to Koebe, Andreev and Thurston that has some bearing on the disk packing puzzle. Bill had some ideas on how to prove my conjecture on a strategy for designing disk packing puzzles that have unique solutions. His emails to me contained detailed arguments and even sketches and were carefully worded to be comprehensible to a physicist. We should all follow his example in freely sharing our insights with others.