- n ≥ 5: Smale, 1960 (and Stallings at around the same time)
- n = 4: Freedman, 1980
- n = 3: Perelman, early 2000s (this is the Poincare conjecture)
- n = 2: "follows from the Riemann mapping theorem"
- n = 1: "a nice exercise for an undergraduate"
So in low dimensions the problem is easy, or at least doesn't require "modern" apparatus; in high dimensions it's harder (Smale and Freedman both got Fields Medals); in "middle" dimensions (like 3) it's the hardest, or at least took the longest. It's my understanding that it's pretty typical in geometry/topology for the three- or four-dimensional cases of a problem to be the most difficult?
Can you think of other problems (from any area of mathematics) that have a similar property -- that they're hardest for some medium-sized value of whatever a natural parameter for the problem is? (Yes, it's a vague question.)
15 comments:
Classifying exotic differentiable structures
I think the notion of dimension is really important here. The point is, if the dimension is too small, there's nothing going to happen; if it's too big, anything can happen (and therefore there aren't as many interesting structures).
I'm not sure what other "natural parameters" would have that property. Smoothness maybe? Continuous functions on the one easy end, C^2-and-above on the other easy end, and not-quite-C^2 in the middle?
Donoho and Tanner have a recent paper discussing problems that get easier in higher dimensions.
Can you think of other problems (from any area of mathematics) that have a similar property -- that they're hardest for some medium-sized value of whatever a natural parameter for the problem is?
This comes up all the time with phase transitions. Typically there will be some physical parameter (temperature, density, etc.) where at both extremes the behavior is simple, but it's different at the two extremes, and the transition between them can be much more complicated. Determining precisely where the transition is, or what happens nearby, can be much harder than analyzing the behavior far from the transition.
there's a neat Erdos problem: what's the maximum number of pairs of points that can be a unit distance apart, maximized over all point sets of size n.
The problem is easy in 1D (linear) and beyond (quadratic). Figuring out the right bound in 2D (currently n^{4/3} and 3D (currently n^{3/2}) is a vexing problem in combinatorial geometry.
I'm not sure this is exactly what you're looking for, but the kissing number has been known for 8 and 24 dimensions for some time, but was resolved for 4 dimensions only quite recently, and is still an open problem in all n>4 *except* 8 and 24.
The kissing number problem is an interesting example. The reason dimensions 8 and 24 are solved is due to the existence of exceptional structures: the Leech lattice, the octonions, and so forth. On the other hand, one reason to single out dimensions 3 and 4 geometrically is the existence of exceptional structures in those dimensions: the dodecahedron, icosahedron, 24-cell, 120-cell, and 600-cell. And morally these (and other exceptional structures in mathematics) are closely related.
Perhaps exceptional structures recur in different branches of mathematics for the same underlying reason related to this "intermediate parameter" idea; in low-parameter regimes one expects local obstructions and in high-parameter regimes one expects global obstructions, or something like that. For example, any sufficiently small finite simple group must be abelian), and any sufficiently large finite simple group must be non-sporadic.
Off the top of my mind i can think of the n-body problem (which has been dealt with for the n=[2,3] cases but not truly for n>3) and the Small World property emerging in some graphs.
This is in fact close to what an anonymous commenter posted above...It's a phase transition.
The beta network model by Watts-Strogatz can produce random networks ranging from an ordered lattice to a completely random structure depending on a parameter (p). When p=0 you get a lattice network. When p=1 you get a random network. Networks produced for intermediate values of p had not been studied until recently (1998) and lead to the realisation of the Small Word Property through an investigation of the Clustering Coefficient and Mean Path Length statistics.
Possibly the classification of all finite simple groups? My memory is that the early proofs centered around either classifying all finite simple groups of order less than some N, or classifying all finite simple groups of order more than some other N, and that the final proofs filled in the middle values until the two bounds met.
While we're on the subject of the classification, Ars Mathematica has a post I think is relevant. JacquesC's comment about "room" is opposite, but I think complementary, to what I wrote. It all depends on whether you think the exceptional structures or the asymptotic structures are the interesting ones. (Litmus test: how do you feel about the exceptional outer automorphism of S_6?)
I remember noticing this phenomenon in statistical mechanics; it was always easier to prove from first principles that various real-world phenomenon would happen in 2 or 4 dimenstions than in 3.
So then I see all this string theory stuff about how the universe started with 11 dimensions and quickly collapsed down to 3 of space and 1 of time. Is there any possible link here? That the universe had to stop collapsing at three dimensions because the a three-dimensional universe is too complex?
pciszek: as I understand it, string theory has no good explanation for why we ended up at 3 spatial dimensions instead of 2 or 4 or some other number. It's just one of many (about 10^500) parameters on the theory that was originally supposed to have at most one parameter.
This is only tangentially related, since the problem isn't really much harder in intermediate dimensions, but of course dimensions 3 and 4 have exceptional regular polytopes. (Which I just now see Qiaochu already mentioned).
A natural example of phase transition occurs, of course, in the theory of random graphs. For instance, if the number of edges is big or small compared to n log n, then a graph is almost certainly Hamiltonian; in a range around n log n, though, not much can be said.
Would the dichotomy between structure and randomness count as a "meta" example? In combinatorics, we often know how to deal with objects that are very structured and with objects that are "random," but you need powerful tools such as the regularity lemma to deal with objects that are neither fully structured nor (pseudo)random.
Hehehehe... here's a problem that fits the letter of the challenge, if not the spirit.
Problem: Find a set with cardinality X.
Easy for X <= |N|, easy for X = |R|, hard in between. ;)
Loop-erased random walk on Z^d is a good example. It's known what the scaling limit is for d=2 (SLE_2), d\geq 5 (Brownian motion), d=4 (Brownian motion with a scaling factor), but not d=3. The high dimensional cases were handled by studying the intersections of random walks, but completely new techniques were required for d=2, and completely new techniques will likely be required for d=3.
Post a Comment