August 2010 - mathfun@mailman.xmission.com

[math-fun] Commutapult: Catapulting Commuters
by Henry Baker 10 Aug '10

10 Aug '10

FYI -- I had a similar idea a number of years ago to provide "cheap" L.A./SF flights. Relatively long acceleration & deceleration ramps required to keep passengers alive. Some significant problems in recovering the energy involved to reuse in next flight. Also, even minor changes due to air pressure/temperature can affect where the vehicle lands, so some steering mechanism is required. http://www.commutapult.org/

4 4

Re: [math-fun] Vinay Deolalikar claimed proof that P != NP
by Dan Asimov 09 Aug '10

09 Aug '10

This sounds to me like saying someone did not situate a window well if it was eventually smashed by a wayward baseball. --Dan << It is well documented that Einstein did not invest the money well, and most of it was lost in the Depression. >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Combinatorics question: Counting placing items in bins according to boolean restrictions
by Paul Reiners 09 Aug '10

09 Aug '10

We have a pool of items. Each item has a set of characteristics. Each characteristic is either a string, integer, or floating-point number. Each item is also of a particular type. Types are hierarchical. We also have a set of bins. Each bin has a requirement, which is a boolean expression comprised of atomic expressions regarding item characteristics. These atomic expressions can be string, integer, or floating-point comparisons and type comparisons. We wish to put the items in the bins such that each item placed in a bin satisfies the requirement of that bin. Each bin also must contain a specified number of items. For example, we might have the following type hierarchy: - shape - triangle - equilateral triangle - rectangle - square We could have the following items: - LargeRedTriangle - type = triangle - color = "red" - area = 1000 - SmallShape - type = shape - area = 5 - LargeBlueSquare - type = square - color = "blue" - area = 2000 Here is an example bin: - LargeRectangles - (type == rectangle) and (area > 750) - item count = 5 We could put LargeBlueSquare in the LargeRectangles bin. We want exactly 5 items in this bin. Here is another example bin: - NonBlueTriangles - (type == triangle) and (not (color == "blue")) - item count = 10 LargeRedTriangle can go in the NonBlueTriangles bin. We want exactly 10 items in this bin. So, we have a set of items and a set of bins. The question is to find out how many ways there are to put the items in the bins while satisfying the constraints (i.e., the requirements for items in bins and the number of items in each bin). (We don't need to enumerate all the ways to do this; we only need to know how many different ways of doing this there are.) Is there an efficient way of determining this number? Or do we just have to 'brute-force' it and try every possible combination? (For what it's worth, this is a question that came up at the software company I work at. I tend to think there is no efficient solution, but I'm looking for a good argument in favor of that. (Or, even better, an efficient way of computing this.)

2 4

Re: [math-fun] Vinay Deolalikar claimed proof that P != NP
by Henry Baker 09 Aug '10

09 Aug '10

I recently heard a radio program which claimed that Einstein's 1921 Nobel prize was one of the most valuable ever granted, after adjusting for inflation & currency fluctuations. After doing a web search, however, I have been unable to find the reference. Perhaps one of you knows? It is well documented that Einstein did not invest the money well, and most of it was lost in the Depression. At 07:29 AM 8/9/2010, Thane Plambeck wrote: >Scott has offered to kick in $200K on top of the Claymath $1M prize if the proof is correct > >http://scottaaronson.com/blog/?p=456 > >On Mon, Aug 9, 2010 at 7:21 AM, Steve Rowley <sgr(a)alum.mit.edu> wrote: > >> Scott Aaronson wrote a nice, not-too-complexity-theory-techical paper >> about the implications with soap bubbles, Steiner trees, what can work >> & what can't in quantum computing, and a number of other things: >> >> S Aaronson, "NP-complete Problems and Physical Reality" >> http://www.scottaaronson.com/papers/npcomplete.pdf >> >> >Date: Sun, 8 Aug 2010 19:54:15 -0700 >> >From: Kerry Mitchell <lkmitch(a)gmail.com> >> > >> >Assuming for the moment that the proof holds up, what are the implications of P != NP? >> > >> >On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber(a)gmail.com wrote: >> > >> >> Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP. >> >> >> >> Paper at >> >> >> >> http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf<http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> >> <http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> >> >> http://www.scribd.com/doc/35539144/pnp12pt >> >> >> >> Some discussion at >> >> >> http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_n… >> -- >> Steve Rowley <sgr(a)alum.mit.edu> http://alum.mit.edu/www/sgr/ Skype: sgr000 >> It is very dark & after 2000. If you continue, you are likely to be eaten >> by a bleen. > >-- >Thane Plambeck >tplambeck(a)gmail.com >http://thaneplambeck.typepad.com/

1 0

[math-fun] Squared Rectangle Puzzles
by Ed Pegg Jr 09 Aug '10

09 Aug '10

Rectangles made entirely of squares can be wonderful problems. Bill Gosper: "Search the Web for 'squared rectangles'. If I were king, one of these diagrams (undimensioned) would appear daily in the newspaper puzzle pages." http://tweedledum.com/rwg/rectarith12.pdf http://gosper.org/Googebra.htm (Solving techniques) I made a few thousand puzzles involving Squared Rectangles. In each case, the dissection is "nowhere neat", in that no two squares share a full edge. Also, all of the squares in each dissection have a size less than 100. I give two different types of puzzle for each dissection. http://demonstrations.wolfram.com/MondrianPuzzles/ I also attach a large scale puzzle of this type, as a challenge. The squared rectangle it produces is extremely tiny. I'm willing to bet $20 that an asymmetrical, nowhere-neat, squared rectangle of an equal or smaller size and more squares is impossible. A proof would be straightforward and impossible -- just run Bouwkamp processing on all gajillion planar graphs with 54 to 90 edges. At 35 edges, there are already 5986979643542 planar graphs. http://www.numericana.com/data/polycount.htm More history and solving techniques at http://squaring.net/sq/tws.html --Ed Pegg Jr http://www.mathpuzzle.com/

1 2

[math-fun] Vinay Deolalikar claimed proof that P != NP
by Michael Kleber 09 Aug '10

09 Aug '10

Vinay Deolalikar sent out email Friday night with a claimed proof that P != NP. Paper at http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf http://www.scribd.com/doc/35539144/pnp12pt Some discussion at http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_n… including the comment that "the original email he sent out was to very well known complexity theorists at schools like stanford, berkeley, mit, princeton, etc (cook, sisper, vazirani, donaldson, etc)" Text of his email: Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts. The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof. This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible. This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. Comments and suggestions for improvements to the paper are highly welcomed. Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs -- Forewarned is worth an octopus in the bush.

7 6

Re: [math-fun] Vinay Deolalikar claimed proof that P != NP
by Henry Baker 09 Aug '10

09 Aug '10

I haven't yet had a chance to read/understand the paper, but I'm not aware of anyone who seriously thought that P was equal to NP. A proof of P=NP would have been world-shattering. Proofs of stuff that people already assume are true usually have impact through their novel proof procedures/methods. Here, I would imagine that the main advance of the proof will be to formalize the model, so that people can start making changes to the model & thereby find models where the proof doesn't work. In those models, either things become a lot more interesting, or additional proof methods are required. Rinse & repeat. For example, I'm interested in finding out to what extent quantum computing is covered in these models. At 07:54 PM 8/8/2010, Kerry Mitchell wrote: >Assuming for the moment that the proof holds up, what are the implications >of P != NP? > >Kerry Mitchell > >On Sun, Aug 8, 2010 at 5:47 PM, Michael Kleber <michael.kleber(a)gmail.com>wrote: > >> Vinay Deolalikar sent out email Friday night with a claimed proof that P != >> NP. >> >> Paper at >> >> http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf<http://www.win.tue.nl/%7Egwoegi/P-versus-NP/Deolalikar.pdf> >> http://www.scribd.com/doc/35539144/pnp12pt >> >> Some discussion at >> >> http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_n… >> >> including the comment that "the original email he sent out was to very well >> known complexity theorists at schools like stanford, berkeley, mit, >> princeton, etc (cook, sisper, vazirani, donaldson, etc)" >> >> >> Text of his email: >> >> Dear Fellow Researchers, >> >> I am pleased to announce a proof that P is not equal to NP, which is >> attached in 10pt and 12pt fonts. >> >> The proof required the piecing together of principles from multiple areas >> within mathematics. The major effort in constructing this proof was >> uncovering a chain of conceptual links between various fields and viewing >> them through a common lens. Second to this were the technical hurdles faced >> at each stage in the proof. >> >> This work builds upon fundamental contributions many esteemed researchers >> have made to their fields. In the presentation of this paper, it was my >> intention to provide the reader with an understanding of the global >> framework for this proof. Technical and computational details within >> chapters were minimized as much as possible. >> >> This work was pursued independently of my duties as a HP Labs researcher, >> and without the knowledge of others. I made several unsuccessful attempts >> these past two years trying other combinations of ideas before I began this >> work. >> >> Comments and suggestions for improvements to the paper are highly welcomed. >> >> Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs

1 0

Re: [math-fun] 5000 billion digits of Pi
by Dan Asimov 08 Aug '10

08 Aug '10

James C.: << DA> Has anyone listed the largest terms in Hans's data? The GM? . . . . . . >> Those are good questions, but they weren't mine. (I asked about how the CF expansion of pi compared with a "statistically expected" one . . . and then someone pointed out that dependence among nearby quotients makes this tricky to define. But I'm still curious about the answer, if someone knows a better way to ask the question. And maybe in the limit, it suffices to just examine the frequency of various quotients, anyway. Since I think the effect of one quotient on the distribution of nearby ones diminishes quickly.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] 5000 billion digits of Pi
by Dan Asimov 08 Aug '10

08 Aug '10

Okay, so a natural question is whether the CF quotients have the "expected" distribution. In the invariant measure* on (0,1], the number N has probability P(N) = log_2( 1 + 1/(N(N+2)) ) So how does this compare with the calculation for pi ? --Dan * I.e., with density d(x) = (1/log(2)) 1/(x+1), invariant under the map T(x) = 1/x - [1/x]. _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

4 3

Re: [math-fun] 5000 billion digits of Pi
by Dan Asimov 07 Aug '10

07 Aug '10

I think I'm missing something. --Dan << In the invariant measure* on (0,1], the number N has probability P(N) = log_2( 1 + 1/(N(N+2)) ) * I.e., with density d(x) = (1/log(2)) 1/(x+1), invariant under the map T(x) = 1/x - [1/x]. _____________________________________________________________________ << Correction: P(n) = (1/log 2) log((n+1)^2/n(n+2)). >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1