Explosions – now in glorious 2D!

Dennis Sullivan tells the story of attending a dynamics seminar at Berkeley in 1971, in which the speaker ended the seminar with the solution of (what Dennis calls) a “thorny problem”: the speaker explained how, if you have N pairs of points in the plane (all distinct), where each pair is distance at most apart, the pairs can be joined by a family of N disjoint paths, each of diameter at most (where depends only on , not on N, and goes to zero with ). This fact led (by a known technique) to an important application which had hitherto been known only in dimensions 3 and greater (where the construction is obvious by general position).

Sullivan goes on:

A heavily bearded long haired graduate student in the back of the room stood up and said he thought the algorithm of the proof didn’t work. He went shyly to the blackboard and drew two configurations of about seven points each and started applying to these the method of the end of the lecture. Little paths started emerging and getting in the way of other emerging paths which to avoid collision had to get longer and longer. The algorithm didn’t work at all for this quite involved diagrammatic reason.

The graduate student in question was Bill Thurston.

I had heard Dennis tell this story before on more than one occasion, but never payed quite enough attention to the precise mathematical claim the speaker was making, or exactly what Thurston’s counterexample could have been. I was also never sufficiently intrigued to wonder what the applications of this claim to dynamics might have been.

A few weeks ago, Marty McFly (name changed to protect the innocent) emailed me, saying that this question had occurred to him while preparing the proof of the Oxtoby-Ulam theorem (a generic measure preserving map of the square has a dense orbit) for presentation in class, and speculating that it might have been the question that Bill counterexampled in Sullivan’s anecdote. We had some back-and-forth on it, and then decided that it must have been a different question, because as far as we could tell, the claim about connecting nearby points by paths of small diameter is true. 

Further clarification in email with Sullivan shows that this was indeed the question in the anecdote, and that Bill had not demonstrated a counterexample to the statement of the claim, but to show that the argument presented by the speaker was wrong. Apparently, a correct proof had been worked out not too long afterwards, Sullivan thought maybe by Bob Edwards, with the optimal constant.

So out of curiosity, I thought I would try to find out what the dynamical applications of this statement might be, and I thought it could be useful to present the statement of the application, and the (cute) proof of the claim that I worked out while corresponding with Marty.

We must go back in time to a 1972 Annals paper by Shub-Smale, entitled Beyond hyperbolicity. Suppose we have a compact smooth (i.e. ) manifold M, and a diffeomorphism (where is fixed in the sequel) and we are interested in the “stability” of f under perturbations in the space of diffeomorphisms of M. Associated to any diffeomorphism f is the nonwandering set , defined to be the closed invariant subset of points x in M with the property that for any open neighborhood U of x there is a positive m such that intersects U. It is a natural question to try to find necessary and sufficient conditions on f such that the nonwandering set of f is “stable”, in the sense that for any open neigborhood U of , there is a neighborhood of f in the space of diffeomorphisms of M (in the topology!) so that for all . If f has this property, we say that f does not permit explosions. The main purpose of the Shub-Smale paper is to introduce the notion of a fine sequence of filtrations, and to prove that a diffeomorphism possesses a fine sequence of filtrations if and only if it does not permit explosions.

The actual definition of a fine sequence of filtrations is a bit technical and unenlightening;  its main properties are that it is manifestly stable under perturbations, and that it controls the way the nonwandering set can vary. The definition of a fine sequence of filtrations generalizes the definition of a fine filtration, which guarantees no explosions, but is strictly stronger, as witnessed by an example due to Newhouse. As Marty remarked to me in email,

Sheesh, apparently the Annals used to publish just about *anything*… ;^)

In fact, Shub-Smale do not even prove the equivalence of the existence of a fine sequence of filtrations and the no-explosions property in full generality, since there is a key point in their argument in which they need to assume that the dimension of M is (you guessed it) at least 3. So this is the mysterious “important application” that the unnamed Berkeley dynamics seminar speaker wanted to establish: the equivalence of the two conditions for diffeomorphisms of 2-manifolds.

Before I give the short proof of the missing proposition, I should say that with some detective work, I believe that a Lemma, implying the desired application, can be found in a paper of Nitecki-Shub from 1975. This is Lemma 13 in their paper, which depends on an earlier Lemma 9 in the same paper (they remark that the same result was proved independently by S. Blank, but they don’t say how, and there is no reference). The statement of the Lemma is the following:

Lemma (Nitecki-Shub): Let M be a manifold of dimension at least 2. Suppose we have pairs of points all distinct (say), where the distance from to is at most for each i. Then there is a diffeomorphism f of M taking each to , and such that the distance from x to f(x) is at most for every point x.

Notice that this is implied by, though weaker than, the claimed result in the dynamics seminar, though with a (presumably optimal) explicit constant .

Anyway, after all this, I hope that I have motivated the proof of the following proposition:

Proposition: Let X and Y be finite disjoint subsets of the plane, and suppose there is a bijection f from X to Y such that the distance from x to f(x) is at most R for all x in X. Then there is a collection of disjoint embedded paths in the plane, each of diameter at most 42R, joining each x to f(x).

We first prove two Lemmas:

Lemma 1: With notation as above, we can partition X into three disjoint sets so that for each there is a collection of disjoint embedded paths joining each x to f(x), for all x in , and such that every path in has diameter at most 6R.

Proof of Lemma 1: We can tile the plane by regular hexagons, each of diameter 4R, and 3-color the hexagons so that hexagons with the same color are distance at least 2R apart (see figure). Let be the points of X in the hexagons colored with the th color, for . Each hexagon H is contained in a bigger hexagon H’ of diameter 6R so that if x is in H, then f(x) is in H’; moreover, for A,B hexagons of the same color, the bigger hexagons A’,B’ are disjoint. Now, for each hexagon H, we can simply join the points of X in H to their images in H’ by any embedded path in H’; any finite set of embedded paths has connected complement, so this can be done, and each path has diameter no bigger than the diameter of H’, which is 6R. Since big hexagons A’,B’ of the same color are disjoint, the paths in different big hexagons don’t intersect. qed.

Tiling of the plane by hexagons of diameter 4R

Lemma 2: Suppose P is a collection of disjoint paths in the plane all with diameter at most D, and Q is a collection of disjoint paths in the plane all with diameter at most D’. Suppose endpoints of P and Q are disjoint. Then there is a collection Q’ of disjoint paths joining the same pairs of points as Q, so that P and Q’ are disjoint, and every path in Q’ has diameter at most D’+2D.

Proof of Lemma 2: Let N be the union of disjoint narrow disk neighborhoods of the paths in P. We can suppose that the endpoints of Q are not in N. There is a homeomorphism h of the plane, supported in N, taking each component of N to itself and shrinking everything except a tiny collar of the boundary down to an extremely small neighborhood of the center. The image of P under h is thus as close as we like to a discrete set of points, so we may perturb Q an arbitrarily small amount to be disjoint from . So apply to this perturbed Q to obtain Q’, and observe that each path in Q’ is within the D-neighborhood of some path in Q. qed.

Proof of Proposition: Apply Lemma 1 to obtain collections of disjoint embedded paths, all with diameter at most 6R. Apply Lemma 2 to to obtain embedded and disjoint from all with diameter at most 18R. Apply Lemma 2 to to obtain embedded and disjoint from and from all with diameter at most 42R. qed

After all this, I am curious about the following questions:

• What was Bob Edwards’ proof (if it was Bob Edwards)? What is the optimal constant?
• Are there any applications of the stronger Proposition that are not implied by the Nitecki-Shub (-Blank) Lemma?
• Are fine sequences of filtrations (or explosions for that matter) important in dynamics these days?
• Who was the mystery speaker at the Berkeley seminar, what was their argument, and what was Bill’s counterexample???

Answers to any of these questions would be greatly appreciated!!

(Update November 10:) Bob Edwards emailed me a link to a different solution, appearing in the American Mathematical Monthly. It was posed as a problem by J. L. Bryant, and solved by Peter Ungar; an editorial note at the end suggests that the best constant is for arbitrary !