August 2012 - mathfun@mailman.xmission.com

[math-fun] elliptic curve calculator
by Warren Smith 29 Aug '12

29 Aug '12

Why is this better than a slide rule?

2 1

[math-fun] Probability a biased random walk returns to start point
by Warren Smith 29 Aug '12

29 Aug '12

Consider a random walk on a D-dimensional cubic lattice (all nearest neighbors equally likely at next timestep). It is well known that if D<=2 the walk eventually returns to its startpoint with probability=1, while if D>=3 the return probabilities R obey 0<R<1. Now let us BIAS the random walk so that the expected motion after 1 step, is nonzero. (All 1-step probabilities independent identical and time- and space-independent.) In we still always walk only to nearest neighbors, then I claim that the return probability is always strictly below 1, in any dimension. Now if we permit walk-steps to go to NON-nearest neighbors, then it gets more interesting because probability distributions whose variances are infinite, or whose means are undefined, could be considered. For example, if in each dimension you walk to a Cauchy-distributed point centered at current location (fixed up so it is discrete not continuous...), then I claim the return probability R is 1 in 1 dimension but 0<R<1 in dimensions>=2. But I nevertheless claim that if the expected hop exists and is nonzero, then in any dimension the return probability is strictly below 1. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Turing machine gives order to chaotic Penrose universe
by Henry Baker 29 Aug '12

29 Aug '12

FYI -- http://www.newscientist.com/article/dn22222-turing-machine-gives-order-to-c… New Scientist Physics & Math Turing machine gives order to chaotic Penrose universe 15:23 29 August 2012 by Jacob Aron A theoretical computer built in a mixed-up mathematical universe might not sound like the most practical invention. But the discovery shows that computation can turn up in the most unlikely places, which in turn might spur more realistic models of physical and chemical processes. The computer is what's known as a universal Turing machine, a theoretical construct invented by mathematician Alan Turing that's capable of simulating any computer algorithm. The computers we use today are approximations of Turing's idealised machine. Katsunobu Imai at Hiroshima University in Japan and colleagues have found a way to bring Turing's computational order to an irregular universe based on Penrose tiles Â a feat that was considered highly improbable until now. Named after mathematician Roger Penrose, the tiling is an arrangement of two four-sided shapes called a kite and a dart, which covers a two-dimensional plane, without repeating, to create a constantly shifting pattern. The team used this mathematical playing field to make a cellular automaton, a two-dimensional universe in which patterns of cells evolve to create complex structures. The most famous cellular automaton is the Game of Life, a grid of identical square cells that can either be "alive" or "dead". Players have created universal Turing machines in the Game of Life's orderly, two-state universe. But making one work in a more chaotic Penrose universe presented a greater challenge to Imai's team. Wired tiles The scientists constructed logic gates for their universal Turing machine by assigning one of eight different states to each Penrose tile, with the states changing over time according to a few simple rules. Tiles in the first state act as wires that transmit signals between the logic gates, with the signal itself consisting of either a "front" or "back" state. Four other states manage the redirecting of the signal within the logic gates, while the final state is simply an unused background to keep the various states separate. At first it wasn't clear whether Imai's team would be able to keep their logic gates wired together, as the gates can only appear in certain places where the tiles come together in the right way. However, the team found that a long enough wire would always make the connection, proving that a universal Turing machine is possible in the Penrose universe. Imai will present the work next month at the Automata conference in La Marana on the French island of Corsica. More natural modelling Earlier this month, researchers also made the unexpected discovery of a highly repetitive object called a glider in the Penrose universeMovie Camera. http://www.newscientist.com/article/dn22134-first-gliders-navigate-everchan… Gliders actually form the basis for a universal Turing machine in the Game of Life, shuttling information around in place of wires. Imai didn't know about the Penrose glider at the time, so he was forced to take an alternative approach. Susan Stepney, a computer scientist at the University of York, UK, says Imai's creation is not very practical as it requires a theoretically infinite number of cells to function. Still, Imai says he was inspired to try and make a universal Turing machine because he wanted to probe the limits of complexity in a Penrose universe. Just showing that it's possible could open the door to other, more useful applications, he says. "Cellular automata are widely used for modelling physical and chemical phenomena, but sometimes the resulting patterns are quite artificial," he explains. While grid-based patterns don't really reflect the natural world, the irregular patterns in Penrose tiling could provide a better model. Journal reference: arxiv.org/abs/1208.2771v1 http://arxiv.org/abs/1208.2771v1

1 0

[math-fun] random feasibility
by Veit Elser 29 Aug '12

29 Aug '12

Let A be an m x n matrix with entries drawn from a normal distribution with zero mean. The probability that the set of linear inequalities A.x > 0 has a solution (for the n-component vector x) is a fun calculation (try it!) and, I'm told, was first worked out by Ludwig Schlaefli. For large m and n the probability switches abruptly from 1 to 0 as the ratio m/n passes through 2. There is a similar phenomenon for the much harder problem of random 3-SAT formulas, where they abruptly become unsatisfiable when the ratio of clauses to variables crosses a threshold. In that problem it is hardest, computationally, to determine satisfiability right at the transition. Does the easier linear programming problem have a similar complexity peak at the transition? -Veit

1 0

Re: [math-fun] zooming in on the reals
by Henry Baker 29 Aug '12

29 Aug '12

Google is full of math folks. I would imagine that someone there could produce what you want in a few minutes. Something like "Powers of Ten". Perhaps Google might be interested in adding this to Google Earth (along with Google Moon, Google Mars, Google Titan, ...). You could add jpeg images ("Here's the picture I took of pi/2 on my last vacation there"), etc. I'm thinking about doing some crude animations (animated gif's?) with inversions to demonstrate how Euclid's algorithm works in the complex plane, but it won't be as pretty as what someone who has access to serious graphics technology could do. At 06:24 AM 8/29/2012, James Propp wrote: >Has anyone created interactive software that lets one zoom in on the real line? > >(One possible design would be an inverse symbolic calculator connected >to a Google Maps interface.) > >Jim Propp

1 0

[math-fun] max |determinant| for 39x39 circulant sign matrix
by Warren Smith 28 Aug '12

28 Aug '12

N=39 |det|=6.321982650572251100739224469504e30 circ=--+-+++-+++--++++-+-++-+----+---+-+++++ grle= -2.92600708563298503e+22 Tomas Rokicki also found this, and his exact determinant was 6321982650569688652881686691840 which is 2562447857537777664 smaller than my computer said, thus exactly revealing the extent of roundoff error. My computer thus got only 12 significant figures correct.

1 0

Re: [math-fun] Handicap go
by Ray Tayek 28 Aug '12

28 Aug '12

At 06:48 AM 8/28/2012, you wrote: > > I posed Warren Smith's puzzle to a group of people who play go online, to > > see if they could improve on his symmetrical answer. Alas, they broke it > > with a quadruple-ko bombshell ... > > http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=20&topic=340 > > >... you may be better of starting with http://senseis.xmp.net/?AtariGo and proving something about that. regarding the http://senseis.xmp.net/?Superko rule, i think that it should be qualified so that the difference in the number of prisoners must be the same (i.e. if the score is changing, do not invoke the superko rule). thanks --- co-chair http://ocjug.org/

1 0

[math-fun] max |determinant| for 38x38 circulant sign matrix
by Warren Smith 28 Aug '12

28 Aug '12

N=38 |det|=4.39152787578415089e+29 circ=-++-++---+---+-+--++----+-----++++-+-+ (For N=38 the computer says grle=-6002933426.61867619 whereas really the Graham-Lehmer number is exactly 0, which shows that a lot of roundoff error has crept in.)

2 1

[math-fun] Handicap go
by Warren Smith 28 Aug '12

28 Aug '12

> I posed Warren Smith's puzzle to a group of people who play go online, to > see if they could improve on his symmetrical answer. Alas, they broke it > with a quadruple-ko bombshell which leads to a draw (or an anullment of the > game). However, slow progress is being made getting the number back down > from astronomical levels: > http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=20&topic=340 > > Alas, I know next-to-bugger-all about go, so can't actually contribute > anything to the discussion myself, but can at least mediate the mathematical > fun aspects of such a discussion. --indeed, I posted my discovery to an online go forum myself, and it got a surprising refutation from Tuomo Salo 3 dan: http://senseis.xmp.net/?ProvableStrategyForWinningFreePlacement25HandicapGo A 1 kyu then attempted (probably correctly) to produce a 54 stone handicap solution: http://senseis.xmp.net/?ProvableStrategyForWinningFreePlacement25HandicapGo… Both my (wrong) discovery and the refutation and attempts to rediscover the answer, all are quite interesting. Go is a lot deeper than it seems when you learn the amazingly simple rules. In fact, after many years play, go still is a lot deeper than it seems and even the greatest players seem to regard it as inexhaustible.

1 0

[math-fun] Jigsaw cipher
by Adam P. Goucher 28 Aug '12

28 Aug '12

I've amalgamated a jigsaw puzzle and cipher: http://cp4space.wordpress.com/2012/08/28/cipher-1-puzzle-hybridisation/ Enjoy! Sincerely, Adam P. Goucher http://cp4space.wordpress.com/

1 0