May 2014 - mathfun@mailman.xmission.com

[math-fun] opposite of Gray code
by Warren D Smith 29 May '14

29 May '14

The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 in an order such that each differs from predecessor in exactly 1 bit. Q1 (easy). Find an anti-Gray code where each differs from predecessor in exactly p-1 bits. Q2 (not so easy). Find a "mid-gray" code where each differs from predecessor in exactly p/2 bits (p>1 even). Note this is impossible if p is a multiple of 4. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Locally isometric polyhedral embedding of flat torus
by James Propp 28 May '14

28 May '14

Where can I learn about, and see pictures of, polyhedral surfaces in R^3 that are locally flat (the angles at each vertex add up to 360 degrees) and have the global topology of R^2/Z^2? More specifically and concretely, how can I crease and fold a square sheet of paper [0,1]x[0,1] so that I can actually glue (t,0) to (t,1) and (0,t) to (1,t) for every t in [0,1]? Jim Propp

5 10

[math-fun] A different kind of polyhedral "torus"
by James Propp 28 May '14

28 May '14

I believe there's a way to take eight unit cubes and join them edge to edge (so that each cube has two edges that are joined to edges of two neighboring cubes) so that (1) the whole chain of cubes can be collapsed into a 2-by-2-by-2 cube, and (2) the chain of cubes, when pulled open, admits a swimming-through-itself motion. Does such a thing exist? (I think I've played with such a thing but I'm not 100% sure.) Are there photos and/or videos on the web? Jim Propp

1 0

[math-fun] Physicists Prove Surprising Rule of Threes
by Henry Baker 28 May '14

28 May '14

FYI -- 22.7x scalings? (I haven't had time to figure out from this paper the precise formula which produces 22.7 -- apparently the logarithm of something that also involves pi.) http://www.simonsfoundation.org/quanta/20140527-physicists-prove-surprising… www.uibk.ac.at/exphys/ultracold/projects/levt/efimov/SovJNucPhys12.589.efim… Physicists Prove Surprising Rule of Threes Efimov trimers are states of matter that theoretically come in an infinite range of sizes. Experimentalists recently observed consecutive trimers, verifying the strange theory. By: Natalie Wolchover May 27, 2014 More than 40 years after a Soviet nuclear physicist proposed an outlandish theory that trios of particles can arrange themselves in an infinite nesting-doll configuration, experimentalists have reported strong evidence that this bizarre state of matter is real. In 1970, Vitaly Efimov was manipulating the equations of quantum mechanics in an attempt to calculate the behavior of sets of three particles, such as the protons and neutrons that populate atomic nuclei, when he discovered a law that pertained not only to nuclear ingredients but also, under the right conditions, to any trio of particles in nature. While most forces act between pairs, such as the north and south poles of a magnet or a planet and its sun, Efimov identified an effect that requires three components to spring into action. Together, the components form a state of matter similar to Borromean rings, an ancient symbol of three interconnected circles in which no two are directly linked. The so-called Efimov ÂtrimerÂ could consist of a trio of protons, a triatomic molecule or any other set of three particles, as long as their properties were tuned to the right values. And in a surprising flourish, this hypothetical state of matter exhibited an unheard-of feature: the ability to range in size from practically infinitesimal to infinite. ÂItÂs a pretty wild idea,Â said Randy Hulet, a physics professor at Rice University in Houston. ÂYou get this infinite series of molecules.Â Efimov had shown that when three particles come together, a special confluence of their forces creates the Borromean rings effect: Though one is not enough, the effects of two particles can conspire to bind a third. The nesting-doll feature Â called discrete scale invariance Â arose from a symmetry in the equation describing the forces between three particles. If the particles satisfied the equation when spaced a certain distance apart, then the same particles spaced 22.7 times farther apart were also a solution. This number, called a Âscaling factor,Â emerged from the mathematics as inexplicably as pi, the ratio between a circleÂs circumference and diameter. ÂItÂs like layers of an onion,Â Hulet said. ÂYou see molecules at one layer. Peel the layer away, and you see that thereÂs a molecule there 22.7 times smaller. Every time you peel away a layer, you find another molecule.Â Efimov published his theory in a Soviet journal as well as the Western publication Physics Letters B. At first, almost no one believed it. ÂIn the West, these ideas were greeted with great skepticism,Â said Eric Braaten, a theoretical physicist at Ohio State University who was in high school when EfimovÂs paper appeared. Theorists waded into the equations in search of an error. But instead, Braaten said, Âthey became convinced that it was true.Â But even with airtight logic, the theory did not necessarily have to manifest itself in nature. ÂI thought it was way too weird to have any basis in reality,Â said Chris Greene, a physicist at Purdue University who studies Âfew-bodyÂ quantum systems, which consist of only a few particles. And for decades, no one knew whether the theory described real matter. As researchers mulled over where to look for Efimov trimers, Efimov himself emigrated west and became a teaching professor at the University of Washington, where he achieved renown more for shooting a gun in class during a lesson on inelastic collisions than for his outlandish theory. Because the Efimov state is weakly bound and is usually overpowered by other forces, observing it requires precise tuning. Particles must have the peculiar quantum property of being able to collide when they are far apart, beyond the range of the force between them Â a situation analogous to Earth ricocheting off a distant star whose gravity it does not feel. And the particles must have too little energy to wiggle out of formation. Some physicists suspected that an accidental fine-tuning in nature might cause the Efimov state to arise in the guise of the helium-4 atom and in a carbon isotope called the Hoyle state that forms in stars and begets many other elements. But these nuclei were too complex for controlled studies. In 1999, Greene realized that the properties necessary for the Efimov state could be tuned by hand in newly developed ultracold optical traps. Atoms inside these apparatuses could be laser-cooled to a fraction of a degree above absolute zero, limiting their wiggling ability, and a magnetic field could be applied to make them collide at great distances. Rudi Grimm and his group at the University of Innsbruck in Austria managed to create an Efimov trimer for the first time in 2006, building it from a trio of cesium atoms cooled to 10-billionths of a degree above absolute zero. It was a long-awaited triumph for Efimov, who, Grimm recalled, became very emotional when he heard the news. But the result did not decisively prove the theory. ÂWith just one example, itÂs very difficult to tell if itÂs a Russian nesting doll,Â said Cheng Chin, a professor of physics at the University of Chicago who was part of GrimmÂs group in 2006. The ultimate proof would be an observation of consecutive Efimov trimers, each enlarged by a factor of 22.7. ÂThat initiated a new raceÂ to prove the theory, Chin said. Eight years later, the competition to observe a series of Efimov states has ended in a photo finish. ÂWhat you see is three groups, in three different countries, reporting these multiple Efimov states all within about one month,Â said Chin, who led one of the groups. ÂItÂs totally amazing.Â GrimmÂs team observed a second Efimov trimer made of cesium atoms, reporting the results May 12 in Physical Review Letters. The 2006 trimer spanned the width of 1,000 hydrogen atoms, requiring the new one to measure a full micrometer across Â Âa gigantic molecule,Â Grimm said. Each 22.7-times larger Efimov state is also 22.7-squared times weaker, requiring the optical trap to be cooled even further to allow the new state to form. GrimmÂs group perfected its techniques and detected the state at the very edge of experimental limits. Meanwhile, the two other groups managed to observe three consecutive Efimov states by taking advantage of a footnote in the theory: When a trimer is built from a mixture of different particles rather than an identical set, the scaling factor of 22.7 decreases according to the particlesÂ relative masses. In other words, nesting dolls made of atomic mixtures become closer in size, enabling more of them to be observed within the experimental window. Both ChinÂs team and a group led by Matthias WeidemÃ¼ller at the University of Heidelberg observed Efimov trimers of three different sizes, each made of two cesium atoms and a much lighter lithium atom. ChinÂs group posted its paper online in February, and the Heidelberg scientists followed with theirs in March. Both papers, which are still under peer review, reported a scaling factor right around 4.9 for the relative sizes of their trimers Â exactly the adjustment to 22.7 predicted by the theory. ÂWe are very excited about this result,Â Chin said. ÂIn the complicated molecular world, thereÂs a new law.Â The law is a geometric progression of evermore-enormous trios of particles, spanning in a theoretically infinite sequence from the quantum scale to (if the particles were cold enough) the size of the universe and beyond. ÂAlthough we didnÂt see an infinite number of them, thereÂs pretty strong evidence when you see three in a row,Â Chin said. For some, the results mark the end of an era, as well as a starting point. ÂFor the classic Efimov scenario, the story is now basically completed,Â Grimm said. But as a paradigm for looking at few-body phenomena in cold atoms, he said, ÂitÂs like the tip of the iceberg.Â The Efimov state is the most elementary effect in few-body physics, the researchers said, but there are countless others that seem to influence the arrangements of small numbers of atoms: four-, five- and six-body interactions and so on. Scientists think it might be possible to augment some of these effects in ultracold optical traps to produce new bulk properties of matter, such as exotic forms of superconductivity. An improved understanding of few-body physics would also feed into models of more complex systems involving many more particles. But direct practical applications of the Efimov state are limited. For the researchers who have studied the odd yet elegant idea for decades, the main driver of the new research, and its chief delight, is having a final proof. ÂIt is satisfying to really see this magic number, 22.7, coming out,Â said Braaten, who was not involved in the new studies. ÂThere was indirect evidence that all this worked, but actually seeing this discrete scaling factor explicitly in experiment Â itÂs comforting.Â

3 2

[math-fun] Don thinks P=NP
by Tom Duff 27 May '14

27 May '14

http://www.informit.com/articles/article.aspx?p=2213858 In "Twenty Questions for Donald Knuth", Don answers questions from 19 or 20 of his colleagues. Mostly pretty interesting. In #17 he explains why he thinks P=NP. Essentially, if it weren't he thinks we'd likely have a proof by now, and the bound on the required exponent may be unimaginably large. We might never have a constructive proof and indeed may never know a bound on the exponent. (As an analogy he quotes a graph theory problem that is known to have a polynomial-time algorithm, but the algorithm is unknown because we only have a non-constructive proof of one of its prerequisites.) -- Tom Duff. Please do not board the elevator with the robot.

2 1

[math-fun] The binom(n-r,r) remark in Adam's
by Bill Gosper 26 May '14

26 May '14

https://cp4space.wordpress.com/2013/10/24/enumerating-the-rationals/ means that the familiar fractal pattern of Pascal's Triangle mod 2 gosper.org/fusc.png enumerates the rationals! I.e., the column sums of the latter two figures give Dÿkstra's fusc: In[140]:= Table[Sum[Binomial[n - r, r], {r, 0, n}], {n, 0, 17}] Out[140]= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584} In[139]:= Table[Sum[Mod[Binomial[n - r, r], 2], {r, 0, n}], {n, 0, 17}] Out[139]= {1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4} In[137]:= Ratios[%] Out[137]= {1, 2, 1/2, 3, 2/3, 3/2, 1/3, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 5, 4/5} Among all the remarkable properties of Pascal's Triangle, I rank this near the top. Adam's page mentions Newnham. Would that be the famous Alfred E, or is it simply Adam's Anglocentric spelling corrector? Forgetting I had NeilB's Calkin-Wilf accelerator, I foolishly tried to count down 325/36 by reverse Newman: x -> 2 ceiling(x) - x - 1. Hours later, I thought to In[118]:= ContinuedFraction[325/36] Out[118]= {9, 36} In[130]:= fromcf[{9, k}] Out[130]= (1 + 9 k)/k In[131]:= Table[%, {k, 11}] Out[131]= {10, 19/2, 28/3, 37/4, 46/5, 55/6, 64/7, 73/8, 82/9, 91/10, 100/11} In[136]:= noomct /@ %131 Out[136]= {1023, 1535, 2559, 4607, 8703, 16895, 33279, 66047, 131583, 262655, 524799} In[133]:= FindSequenceFunction[%, k] Out[133]= 511 + 2^(8 + k) In[134]:= 9 + 1/36 Out[134]= 325/36 In[135]:= %% /. k -> 36 Out[135]= 17592186044927 promising a rather lengthy wait. It is amazing how relatively congenial Newman is to convergents. Even for sqrt 7, which has period 4: In[259]:= Convergents[Sqrt[7], 16] Out[259]= {2, 3, 5/2, 8/3, 37/14, 45/17, 82/31, 127/48, 590/223, 717/271, 1307/494, 2024/765, 9403/3554, 11427/4319, 20830/7873, 32257/12192} In[260]:= tim[noomct[#]] & /@ % During evaluation of In[260]:= 0.000038,0 . . . During evaluation of In[260]:= 24.287843,0 During evaluation of In[260]:= 60.010885,0 Out[260]= {3, 7, 11, 27, 491, 1003, 1515, 3563, 62955, 128491, 194027, 456171, 8058347, 16446955, 24835563, 58389995} It can do 32257/12192, but not 325/36. FindSequenceFunction readily but messily interlaces the four sequences: In[261]:= FullSimplify[FindSequenceFunction[%, n], n \[Element] Integers] Out[261]= (1/4064)(-3424 + 2^(7 n/4) (221 + 976 2^(1/4) + 498 Sqrt[2] + 188 2^(3/4) + (-1)^ n (221 - 976 2^(1/4) + 498 Sqrt[2] - 188 2^(3/4)) + (442 - 996 Sqrt[2]) Cos[(n \[Pi])/2] + 8 2^(1/4) (244 - 47 Sqrt[2]) Sin[(n \[Pi])/2])) In[262]:= Table[%, {n, 16, 18}] // Simplify Out[262]= {58389995, 1031468523, 2105210347} In[263]:= Convergents[Sqrt[7], 18][[-3 ;; -1]] Out[263]= {32257/12192, 149858/56641, 182115/68833} In[264]:= tim[noomct[#]] & /@ Rest[%] During evaluation of In[264]:= 1050.500020,0 During evaluation of In[264]:= 2107.729563,0 Out[264]= {1031468523, 2105210347} as predicted. --rwg

2 3

[math-fun] pennypacking
by Bill Gosper 26 May '14

26 May '14

Jim [Propp] I have a copy of my book with me and can report the following on the circle packing problem. The first time an extra circle can be inserted is when 329 circles can pack into a 2 by 164 rectangle. For that rectangle there are 101 sets of three circles with a set of 7 circles at adjusted placements on each end, fitting into a 2 by 163.99958... rectangle. The smallest 2 by x rectangle admitting 329 circles has 101 sets of three circles with a set of 13 circles adjusted at each end to fit a 2 by 163.9973967...rectangle. I believe this can be proven minimal. The spacing between like circles of triangular elements is 2+sqrt((sqrt(3)-.75). Coordinates of circle centers is different for the two solutions but the set of adjusted circles can be described as follows. Circles 1, 3, 5 and 7 on the bottom have circles 3 and 7 resting on the bottom edge. Circles 2, 4 and 6 are near the top edge with 2 and 6 touching the top edge. Circle 6 then touches the first triangular group touching the top edge. At the right end of the rectangle circles 323-329 are in the same formation in reverse order. Circles 323 and 327 touch the bottom edge and circles 323 and 328 touch the top edge. I don't have the arrangement involving the 13 circle sets at each end with me. I hope this helps you. I had no intent of keeping me email address secret on math fun. How do I make it public? Happy puzzling Dick [Hess] http://gosper.org/pennies1.bmp and http://gosper.org/pennies2.bmp show respective ends of a 2×200 strip containing 133 triads, with ample room for two more pennies. --rwg

2 2

[math-fun] maximum mobility attainable in othello game (?)
by Warren D Smith 25 May '14

25 May '14

During a search of 100M random-legal-move othello games, found this position with #empties=35 and mobility=28: +---+---+---+---+---+---+---+---+ | . | . | . | . | * | . | . | . | +---+---+---+---+---+---+---+---+ | . | O | . | O | * | O | O | . | +---+---+---+---+---+---+---+---+ | . | . | O | * | * | * | . | . | +---+---+---+---+---+---+---+---+ | . | O | O | * | O | O | O | . | +---+---+---+---+---+---+---+---+ | . | . | * | * | * | O | . | . | +---+---+---+---+---+---+---+---+ | . | . | O | O | O | . | . | . | +---+---+---+---+---+---+---+---+ | . | . | O | * | O | O | O | . | +---+---+---+---+---+---+---+---+ | . | . | . | * | . | . | . | . | +---+---+---+---+---+---+---+---+ -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

Re: [math-fun] Speaking of email addresses
by Richard Hess 25 May '14

25 May '14

Jim I have a copy of my book with me and can report the following on the circle packing problem. The first time an extra circle can be inserted is when 329 circles can pack into a 2 by 164 rectangle. For that rectangle there are 101 sets of three circles with a set of 7 circles at adjusted placements on each end, fitting into a 2 by 163.99958... rectangle. The smallest 2 by x rectangle admitting 329 circles has 101 sets of three circles with a set of 13 circles adjusted at each end to fit a 2 by 163.9973967...rectangle. I believe this can be proven minimal. The spacing between like circles of triangular elements is 2+sqrt((sqrt(3)-.75). Coordinates of circle centers is different for the two solutions but the set of adjusted circles can be described as follows. Circles 1, 3, 5 and 7 on the bottom have circles 3 and 7 resting on the bottom edge. Circles 2, 4 and 6 are near the top edge with 2 and 6 touching the top edge. Circle 6 then touches the first triangular group touching the top edge. At the right end of the rectangle circles 323-329 are in the same formation in reverse order. Circles 323 and 327 touch the bottom edge and circles 323 and 328 touch the top edge. I don't have the arrangement involving the 13 circle sets at each end with me. I hope this helps you. I had no intent of keeping me email address secret on math fun. How do I make it public? Happy puzzling Dick Sent from my iPhone On May 25, 2014, at 7:41 AM, James Propp <jamespropp(a)gmail.com> wrote: > I'm phasing out jpropp(a)cs.uml.edu, so in future correspondence please use > JamesPropp(a)gmail.com . Thanks! > > Jim > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] Speaking of email addresses
by James Propp 25 May '14

25 May '14

I'm phasing out jpropp(a)cs.uml.edu, so in future correspondence please use JamesPropp(a)gmail.com . Thanks! Jim

1 0