tag:blogger.com,1999:blog-264226589944705290.post2464482858357740826..comments2023-02-06T08:11:10.397-08:00Comments on God Plays Dice: Problems that are hard for intermediate values of some parameterMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-264226589944705290.post-82380166999119369272009-07-26T11:36:07.571-07:002009-07-26T11:36:07.571-07:00Loop-erased random walk on Z^d is a good example. ...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.Anonymoushttps://www.blogger.com/profile/16537179277169955312noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-91809513405063713082009-07-11T21:16:59.137-07:002009-07-11T21:16:59.137-07:00Hehehehe... here's a problem that fits the let...Hehehehe... here's a problem that fits the letter of the challenge, if not the spirit.<br /><br /><i>Problem: Find a set with cardinality X.</i><br /><br />Easy for X <= |N|, easy for X = |R|, hard in between. ;)Aaronhttps://www.blogger.com/profile/18281785407407667986noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-1746217341864509022009-07-07T18:14:18.957-07:002009-07-07T18:14:18.957-07:00This is only tangentially related, since the probl...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).<br /><br />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.<br /><br />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.harrisonhttp://harrisonbrown.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-8560118297557047662009-07-07T17:09:01.502-07:002009-07-07T17:09:01.502-07:00pciszek: as I understand it, string theory has no ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-71072580810894309112009-07-07T14:54:53.793-07:002009-07-07T14:54:53.793-07:00I remember noticing this phenomenon in statistical...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.<br /><br />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?pciszeknoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-51302300078110002292009-07-06T23:14:29.338-07:002009-07-06T23:14:29.338-07:00While we're on the subject of the classificati...While we're on the subject of the classification, <a href="http://www.arsmathematica.net/archives/2006/09/24/what-kind-of-thing-is-a-sporadic-simple-group/" rel="nofollow">Ars Mathematica</a> 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?)Qiaochu Yuanhttp://qchu.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-56490393459212920682009-07-06T13:55:53.032-07:002009-07-06T13:55:53.032-07:00Possibly the classification of all finite simple g...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.Flooeyhttp://www.flooey.orgnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-44725552574131743172009-07-06T03:00:57.716-07:002009-07-06T03:00:57.716-07:00Off the top of my mind i can think of the n-body p...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.<br /><br />This is in fact close to what an anonymous commenter posted above...It's a phase transition. <br /><br />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.AAhttps://www.blogger.com/profile/10139788482239218535noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-47302888901739135222009-07-06T01:44:10.126-07:002009-07-06T01:44:10.126-07:00The kissing number problem is an interesting examp...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.<br /><br />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.Qiaochu Yuanhttp://qchu.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-59810225763232449322009-07-05T20:53:32.680-07:002009-07-05T20:53:32.680-07:00I'm not sure this is exactly what you're l...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.Mark Dominushttps://www.blogger.com/profile/17698641253266210249noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-24855903667710949052009-07-05T19:27:53.307-07:002009-07-05T19:27:53.307-07:00there's a neat Erdos problem: what's the m...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. <br /><br />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.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-92082732347509737182009-07-05T19:14:19.757-07:002009-07-05T19:14:19.757-07:00Can you think of other problems (from any area of ...<i>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?</i><br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-42277619761422716902009-07-05T16:06:37.660-07:002009-07-05T16:06:37.660-07:00Donoho and Tanner have a recent paper discussing p...<a href="http://www.maths.ed.ac.uk/~tanner/DoTa_Universality.pdf" rel="nofollow">Donoho and Tanner</a> have a recent paper discussing problems that get easier in higher dimensions.Johnhttp://www.johndcook.com/blognoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-85791895014541502002009-07-05T14:42:03.504-07:002009-07-05T14:42:03.504-07:00I think the notion of dimension is really importan...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).<br /><br />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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-44906054100471012332009-07-05T14:18:15.384-07:002009-07-05T14:18:15.384-07:00Classifying exotic differentiable structuresClassifying exotic differentiable structuresAnonymousnoreply@blogger.com