April 2014 - mathfun@mailman.xmission.com

[math-fun] Banach-Tarski vs scissors
by Warren D Smith 28 Apr '14

28 Apr '14

Banach-Tarski "paradoxes" can include, e.g. cutting a ball into a finite # peices, then reassembling it into two balls (i.e. twice the volume). In order to accomplish this, the"pieces" are non-measurable sets. This is far nastier than the square-circle "paradox" Plouffe mentioned. The main "use" of Banach-Tarski and their successors seems to be in demonstrating that the foundations of mathematics are a dangerous and nasty place, and maybe you shouldn't really believe some of those ZFC axioms... One starts to feel some sympathy with Brouwer and the "constructivists"... In contrast, the phrase "scissors congruence" is usually used to mean something far tamer and also more practical -- one cuts A into a finite number of pieces using "scissors" (i.e. piecewise-smooth boundaries, everything measurable) which then are re-assembled into B. This was already studied by Bolyai who showed that any two polygons with the same area, were scissors congruent. However, Dehn showed in one of the first Hilbert problem solves, that a regular tetrahedron and cube (same volume) are NOT scissors congruent. It is fairly well understood now what is scissors congruent to what in all low dimensions (say, up to 4) and there is at least one entire book giving amazing scissors congruences. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

4 5

[math-fun] How a weak NIST backdoors Diffie-Hellman
by Henry Baker 28 Apr '14

28 Apr '14

FYI -- www.ams.org/notices/201402/rnoti-p190.pdf "The NSA Back Door to NIST" "We give a brief mathematical description of the NIST standard for cryptographically secure pseudo- random number generation by elliptic curves, the back door algorithm discovered by Ferguson and Shumow, and finally the design of the back door based on the Diffie-Hellman key exchange algorithm."

1 0

Re: [math-fun] Novel ways to present proofs
by Adam P. Goucher 27 Apr '14

27 Apr '14

Ross Atkins famously shaved half of his beard so that a picture of his face could be used as an example for teaching people about geometric transformations: the determinant is positive if the beard is on the correct side, and negative otherwise. He once told me how he was talking to someone (after last meeting six months ago), who said, "Wow, Ross, you still have half a beard! You should have switched sides; nobody would notice!" The punch-line is that Ross had indeed switched sides... Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Dan Asimov > Sent: 04/27/14 09:02 PM > To: math-fun > Subject: Re: [math-fun] Novel ways to present proofs > > Ha! As a grad student at Berkeley, I cut off one half of my beard, just for fun, and left it that way for several months. Never thought of the pedagogical applications, though. > > --Dan > > P.S. Nu, so how many hairs *are* in a beard? > > > Veit Elser wrote: > > ----- > beard bisection > > When word came down from on high, “teach them how to estimate”, I > responded by estimating the number of hairs in a beard. At the first lecture > I showed up with a full beard, the second with half shaved off, etc. each > time with yet another half removed. When there was just a few square mm > of beard left we counted the hairs. > ----- > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Double stalemate quest
by Warren D Smith 27 Apr '14

27 Apr '14

Sam Loyd (141-1911) created the shortest (?) chess game ending in stalemate: 19 ply: 1.e3 a5 2.Qh5 Ra6 3.Qxa5 h5 4.Qxc7 Rah6 5.h4 f6 6.Qxd7+ Kf7 7.Qxb7 Qd3 8.Qxb8 Qh7 9.Qxc8 Kg6 10.Qe6 stalemate. A variant of the same length is 1. c4 h5 2. h4 a5 3. Qa4 Ra6 4. Qxa5 Rah6 5. Qxc7 f6 6. Qxd7+ Kf7 7. Qxb7 Qd3 8. Qxb8 Qh7 9. Qxc8 Kg6 10. Qe6. A 24-ply stalemate with NO CAPTURES, also by Loyd: 1. d4 d6 2. Qd2 e5 3. a4 e4 4. Qf4 f5 5. h3 Be7 6. Qh2 Be6 7. Ra3 c5 8. Rg3 Qa5+ 9. Nd2 Bh4 10. f3 Bb3 11. d5 e3 12. c4 f4. As far as I know the minimal length of Loyd's stalemates has not been proven, but seems fairly plausible. I do not know whether a "double stalemate" has ever occurred in a real game. A composed example in 36 ply (Enzo Minerva 2007): 1. c4 d5 2. Qb3 Bh3 3. gxh3 f5 4. Qxb7 Kf7 5. Qxa7 Kg6 6. f3 c5 7. Qxe7 Rxa2 8. Kf2 Rxb2 9. Qxg7+ Kh5 10. Qxg8 Rxb1 11. Rxb1 Kh4 12. Qxh8 h5 13. Qh6 Bxh6 14. Rxb8 Be3+ 15. dxe3 Qxb8 16. Kg2 Qf4 17. exf4 d4 18. Be3 dxe3 and now neither side could legally move. This record might well be beatable by finding one shorter than 36 ply. I posed to some of my friends the question of whether a double stalemate is possible with no captures -- or if captures are necessary, then use as few as possible, and preferably of lower-average mobility men (chessmen ordered by increasing average mobility: PNBRQ) -- and try to create the shortest possible double stalemate game subject to those restrictions. We searched for quite a while, whereupon Monty McGovern found a good looking final position, which I then was able to prove was (a) reachable in a 24-move (48 ply) game, and (b) not reachable in any fewer than 48 ply. This game involves a single capture of a knight by each side, and hence is pretty close to "optimality"... we do not know if a double stalemate is possible using (1,0) or (0,0) captures, or whether you can do it with captures of pawns rather than of knights but I find it plausible those tasks are impossible. Here is the game: Monty McGovern and Warren D. Smith, April 2014 1. b4 Nf6 2. Bb2 h5 3. BxNf6 g5 4. g4 Bg7 5. Be5 b5 6. Bg3 a6 7. Bg2 Bb7 8. Nc3 BxNc3 9. Nf3 Nc6 10. h3 Bd4 11. Nh2 Bb6 12. e4 d4 13. Ke2 Kd2 14. Qg1 Qb8 15. f3 Na7 16. Rf1 Rc8 17. Be1 c6 18. e5 d4 19. Kf2 Bd8 20. a4 Kc7 21. a5 h4 22. c4 f5 23. e6 d3 24. c5 f4 double stalemate. The following URL should show you a picture of the final position: http://www.apronus.com/chess/wbeditor.php?p=A____BRQR___P_KBN___p_P_P_P___p… The proof that 48 ply is shortest possible to reach this position is roughly as follows. You simply add up the shortest-path move-count distances of each piece from its starting to final square (taking account of never-moving pawns as obstacles), plus observe that the Be1 and Kf2 cannot both travel on shortest paths so 1 extra ply needed. That yields a lower bound of 22+22=44 ply. Then you note that the missing Knights have to die somehow, which requires at least 2 extra ply per Knight, because the Ns have to get onto some enemy's shortest path or that shortest path has to gain one extra hop and the N has to get onto that path... reaching 22+22+2+2=48 ply. You also have to take into account the possibility of castling or of using "the other knight" than you think, or of one of the Ns capturing the other... but it is not hard to see these options cannot decrease us below 48. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] a strange result about the squaring of a circle
by Simon Plouffe 27 Apr '14

27 Apr '14

hello, I did not know that such a construction was possible. Apparently there is a way to take a circle and CUT it into pieces a finite number of times and then recombine all this into a circle. http://en.wikipedia.org/wiki/Tarski%27s_circle-squaring_problem the number of such pieces would have to be 10^50. well you have to be patient of course. It uses the axiom of choice. on this I agree : you have to choose or not, Am I crazy enough to undertake such project ?, ha ha ha. Any one know is this makes any sense ? have a good night, here it is 3 a.m. Simon Plouffe

4 3

Re: [math-fun] programming languages...
by Ray Tayek 25 Apr '14

25 Apr '14

At 05:48 PM 4/24/2014, you wrote: >http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html >claims to measure how popular different programming languages are >(currently C is the most popular, with Java a close second). ... there is also: http://www.indeed.com/jobtrends thanks --- co-chair http://ocjug.org/

1 0

[math-fun] double stalemate quest
by Warren D Smith 25 Apr '14

25 Apr '14

I posed the following problem to some of my (former?) friends: play a legal chess game, and reach a "double stalemate" position where neither side has any legal moves. Among all such games, find the one involving the fewest captures, and among all those, the shortest game. Monty McGovern produced a solution involving only 1 capture by each side. If no solutions with (0,1) or (0,0) captures exist, that would mean McGovern's solution is optimal in that sense. Optimization of the length of the game is a worse kettle of fish... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] programming languages...
by Warren D Smith 25 Apr '14

25 Apr '14

http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html claims to measure how popular different programming languages are (currently C is the most popular, with Java a close second). --------- http://golang.org/ includes a 34 minute video giving you a "tour of go" -- go being a programming language brought to us by google. It has a lot of what I want. One gripe: go has no "asserts." * unicode (UTF-8) * considerable similarity to C syntax. They got rid of the ; statement terminator. I like multiple statements on one line. Go will not let you. However, you still are allowed to use ";" optionally, in which case multiple statements on one line are permitted. In some ways the syntax got worse than C, in others better. Mostly I prefer C's syntax. Two improvements in go are int x,y rather than int x, int y in function declarations; and considerable improvement of switch/case. * go got rid of pointer arithmetic. Good move in my view. * go does array bounds checking. Hooray. * go unfortunately failed to implement the superior function declaration+use ideas in Ada. * about arrays: does roughly what I advocate: there are only 1-dimensional arrays, but there can be "slices" (subarrays) * go has meaningful types like uint16, not undefined rubbish like "unsigned short." * Apparently they got rid of "make" (never to be missed) for multi-file programs * go added an "error mechanism" but it seems to be stupid. * go added an "image" graphics IO notion * added thread-spawning concurrency. By default new threads run in the same memory space. * concurrent processes can communicate thru "channels." A thread can send info into, or receive info from, a channel. This automatically causes waiting until the other side is ready. There is a way to listen to multiple channels and act on the first one that has info available. * garbage collection (although, annoyingly, there are two kinds of allocators which seem the same) * interfaces is a "contract" mechanism for specifying purpose without giving the details. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] New Shape Born From Rubber Bands
by Ray Tayek 24 Apr '14

24 Apr '14

http://science-beta.slashdot.org/story/14/04/24/1829232/new-shape-born-from… <http://beta.slashdot.org/%7EUnknown+Lamer>Unknown Lamer posted 3 hours ago | from the sproingees dept. <http://science-beta.slashdot.org/index2.pl?fhfilter=science> Science <http://science-beta.slashdot.org/index2.pl?fhfilter=science> <http://science-beta.slashdot.org/story/14/04/24/1829232/new-shape-born-from…>85 <http://science-beta.slashdot.org/%7Esciencehabit>sciencehabit (1205606) writes "Physicists playing with rubber bands have discovered a new shape. In an attempt to create a spring that replicates the light-bending properties of cuttlefish ink sacs, a team of researchers suspended two rubber strips of different lengths. Connecting the bottoms of the two strips to a cup of water, the shorter band stretched to the same length as the longer one. After gluing the two stretched strips together, the researchers gradually drained the water from the cup. As the bands retracted and twisted from the reduced strain, the <http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0093183>researchers were shocked to see the formation of a hemihelix with multiple rainbow-shaped boundaries called perversions. The team hopes their work <http://news.sciencemag.org/physics/2014/04/video-new-shape-born-rubber-bands>inspires nanodevices and molecules that twist and transform from flat strips into predetermined 3D shapes on demand." There are <http://figshare.com/articles/_Structural_Transition_from_Helices_to_Hemihel…>several videos attached to the original paper, and all can be viewed without flash. --- co-chair http://ocjug.org/

1 0

[math-fun] languages & what is wrong with them continued....
by Warren D Smith 24 Apr '14

24 Apr '14

The fact you can, with great effort, in C++ define a Vector type which checks array bounds, and you can with more-than-usual effort then use it, is WORTHLESS, because just one co-author, just once, in your entire zillion-line 500-file program, uses the obvious default array mechanism, and game over. (JA has drunk the kool-aid to such a great extent, he does not even see the stupidity anymore, & actually thinks this is the way it ought to be.) News flash: safety should not be "achievable with effort." It should be "the default." Unsafety should be what requires excess effort. The fact that so many people, including JA himself, are trying so so so hard for so so long -- years and years of their life expended -- to try to paper over such flaws in the C++ language, is not a sign that it is a great language. It is a sign that it was done wrong. Let us admit the obvious. And what I find even more incredibly astounding, is that he himself does not find this obvious. And yes, a <---> operator for swapping. RW Floyd suggested this in his Turing lecture about how bad languages were. Then the language guys proceeded to ignore him like usual, until we have now reached the point where people like JA actually think this must have been a joke. But I am serious. Commonly used important constructs, should be compact. It is a very simple principle. Language like PASCAL decided to write BEGIN and END everywhere that C just used { }. Very simple and obvious violation of very simple principle. Why? For what possible reason? I mean, were they just sadists? Because I can see absolutely no other reason for it. >How can a language reasonably include "machine language stuff"??? >A (the?) point of C was to get CPU _independent_! --Arggh. The point is: machines do things, and/or should. Some HLLs then try to prevent you from doing that. This is stupid. Correct move: Essentially every operation, which any current or future machine does or likely will/should provide in hardware, should be accessible in the HLL. If your machine does not have it, then that is what HLLs are for -- to emulate it via compilation to a suitable code fragment! If they do not, they they are handicapping not helping you, and they are handicapping not helping future progress because then the hardware designers will see no incentive to actually provide said hardware since "nobody uses it." Does any HLL take this correct attitude? Or does every single HLL take the wrong attitude? This is a huge disaster, and those who've drunk the kool-aid actually think this is the way it ought to be, they've become so wedged. It is so insane. On the bright side, I totally agree with some of the stuff math-funners have said, like Rokicki re SIMD, parallel, and memory/threads issues. Re some other stuff, like C++ templates, in fact my compile-time ideas would do that better. For example, suppose you wrote a SORT routine for int32's. You now want same sort routine but for int64's, int8's etc. OK just do #for( T in {int8, int32, int64} ){ SORT routine defined here using type T } and voila. Here #for is a for loop executed at compile time. You want a compile time language very much like the actual language albeit restricted in power (do not allow it to be turing undecidable whether it compiles... incidentally C++ fails that test and hence should have been dismissed right there; it actually is Turing undecidable whether your C++ program is valid C++, which is just a mind-boggling level of language-design incompetence and incredible testament to how crufty it is).

7 15