July 2012 - mathfun@mailman.xmission.com

[math-fun] New (?) Euclidean algorithm
by Henry Baker 09 Jul '12

09 Jul '12

I've been hacking a new version of the Common Lisp & Maxima "rationalize" function which produces the worst rational approximation to a complex number that falls within epsilon of that complex number. In the case of Maxima, the epsilon is set by the global variable "ratepsilon". The traditional Euclidean algorithm for this process focuses on the number itself (which I call c), and only later worries about the epsilon and the radius of convergence. My algorithm starts with the _circle_ whose center is the given complex number c and whose real radius is r; we can denote this circle by (c,r). Since translation and inversion in the complex plane both take circles to circles (more accurately, "generalized circles" to "generalized circles"), we can perform a Euclidean procedure on the _circle_ (c,r) itself. At each stage we keep track of the transformations (translations & inversions), so that we can recover the original circle, if necessary. We first look at the given circle (c,r). If there is a (Gaussian) integer point within this circle, then we are done, because such a point is rational, so this is our answer. If we compute cr=round(c) (= round(realpart(c))+i*round(imagpart(c))), then this number cr is (one of) the closest integer points to c. If cr is "inside" the circle (c,r), then we are done. Now if r>sqrt(2)/2, then cr _has_ to be inside the circle (c,r). So we now consider the case where cr is not inside (c,r). After translating the origin to cr, we know that this new center is within sqrt(2)/2 from the origin -- i.e., inside the unit circle. We then invert the given circle in the unit circle, which will put the center of that new circle outside the unit circle. Furthermore, the radius of that new circle will grow bigger. We can now compute the closest integral point to the center of that new circle, and so forth. At each of these Euclidean steps, the circle radius grows larger, and must eventually enclose an integral point, at which time we invert the sequence of transformations to compute the final rational answer. This answer will be rational, because the integral point was transformed by inversions and translations by (Gaussian) integers. This discussion is not a _proof_, but shows how the algorithm was conceived. Here's the algorithm in Maxima: euclid(zc,m):= block([q,iqmat], /* zc is input circle in Schwerdtfeger's representation */ /* m accumulates transforms; m starts out as the 2x2 identity matrix */ /* Original circle is always transpose(m^^-1).zc.conjugate(m^^-1) */ q:cround(center(zc)), if is(inside(q,zc)) then m.matrix([q],[1]) else (iqmat:matrix([1,q],[0,1]), euclid(transpose(iqmat.imat).zc.conjugate(iqmat.imat),m.iqmat.imat))); This produces is a column vector matrix([num],[denom]); the result is num/denom. euclid(gcircle(%pi,1.0e-7),ident(2)) produces [ - 122453 ] [ ] [ - 38978 ] = 122453/38978, which is within 10^-7 of pi. (%i13) abs((-122453)/(-38978)-%pi),numer; (%o13) 3.9724384226502707E-8 We use Hans Schwerdtfeger's representation for generalized circles as 2x2 Hermitian matrices. See this Wikipedia article for more details. http://en.wikipedia.org/wiki/Generalised_circle /* We test for "inside" by substituting the point into the equation. */ inside(w,c):=is(equation(c,w)<=0); Although very elegant, there is a problem with Schwerdtfeger's representation for circles: the squared radius of the circle is computed by the difference of two large quantities, so when we approach the limit of machine precision, we may inadvertently end up with a negative number, and hence an _imaginary_ radius! Perhaps this problem can be ameliorated with a slightly different representation.

3 4

[math-fun] continued fractions and circles
by Warren Smith 09 Jul '12

09 Jul '12

To Henry Baker: I point out that just as 1/complex performs an inversion in the unit circle, 1/quaternion and 1/octonion do also in the unit sphere in 4 and 8 dimensions respectively -- up to a conjugation i.e. mirror-reflection in all 3 cases. All of the multiplications in these domains multiply "norms" (sum of squares), i.e. |ab| = |a|*|b|; they are bilinear in dimensions 4 and 8, i.e. c*(a+b)=ca+cb and (a+b)*c=ac+bc; noncommutative in dimensions>=4 (ab .noteq. ba); and non-associative in dimensions>=8 (ab*c noteq a*bc). There also happen to be particularly nice lattices in 2, 4, and 8 dimensions. You favored the square lattice in 2D, but the equilateral triangle lattice is nicer. I can see why you did not want it since 1/2 + i*sqrt(3)/2 is "irrational," but this was a somewhat arbitrary judgment depending on favoring 0+i over that. If we instead favored the eq.triangle lattice ("Eisenstein integers") then the "Gaussian integers" square lattice would be the ones which were "irrational." The Eisenstein integers are just as good as the Gaussians internally speaking, i.e. they are multiplicatively closed, enjoy unique factorization theorem, etc. Your geometric way of looking at things means you can use other lattices essentially as easily as the simple cubic integer lattice. In 4 dimensions, a very nice lattice is the "Hurwitz quaternions" which have all coordinates=integer/2 and sum is integer. Each point has 24 equally-nearest neighbors. It is closed under quaternionic multiplication. In 8 dimensions the nice lattice is the "integral octonions" arising from the E8 lattice. Each point has 240 equally-nearest neighbors. It is closed under octonionic multiplication. Those both enjoy unique factorization theorems albeit the precise forms of these theorems is not immediately obvious and the noncommut and/or nonassoc makes your brain hurt. Given these multiplicative-closure properties, approximating a real octonion x (say) as a "ratio" p/q of octonions, meaning p * inverse(q) = p * conjugate(q) / |q|^2, kind of makes more sense as a goal, i.e. x * q = p and if x were an "integral octonion" (meaning on that lattice, which is not the simple cubic 8D lattice) then x*q would also be. But note q*x and x*q are in general unequal. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] {4, infinity} tiling of H^2 and a generalization of the mediant
by Mike Stay 08 Jul '12

08 Jul '12

In the Poincare half-plane model of hyperbolic 2-space, if we draw the {3, infinity} regular tiling of the hyperbolic plane and put the three points of one triangle at 0, 1, and infinity, then the rest of the points land on Farey fractions. Since the sides are semicircles, each triangle has one high side and two low sides. By placing a vertical line at x, we can read off the continued fraction for x by looking at which of the two low sides of each hyperbolic triangle it passes through---that is, a sequence like LRRRLRRLLL becomes [0,1,3,1,2,3]. What points do we get with the {4, infinity} tiling? For every two points, we'll get two new ones, a "mediant pair". In general, the {n+2, infinity} tiling will have a notion of mediant that gives an n-tuple of points. What's the corresponding notion of continued fraction? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

1 1

Re: [math-fun] math-fun Digest, Vol 113, Issue 7
by Warren Smith 08 Jul '12

08 Jul '12

> From: Ray Tayek <rtayek(a)ca.rr.com> > Subject: [math-fun] ON "ITERATED PRISONER?S DILEMMA CONTAINS > STRATEGIES THAT DOMINATE ANY EVOLUTIONARY OPPONENT" > The highly technical paper, > <http://www.pnas.org/content/early/2012/05/16/1206569109.abstract>" > Prisoner?s Dilemma contains strategies that > dominate any evolutionary opponent" by William H. > Press and Freeman J. Dyson has now been published > in PNAS (May 22, 2012), which was followed by a > PNAS Commentary by Alexander Stewart and Joshua > Plotkin of the Department of Biology, University > of Pennsylvania --based on trying to figure out what they are doing without actually reading it, it seems they are arguing that if the opponent in IPD generates his moves via a Markov chain... which presumably is necessarily true for any real opponent given the laws of physics since that opponent is bounded, i.e. has a finite bounded number of states, and has access to a source of randomness, and hence must be a Markov chain on those states... then you, where by "you" I mean a Turing machine, can outplay him asymptotically by learning his markov model and then predicting his play. This is probably completely irrelevant to real life because the "number of states" of a human being containing 10^27 atoms is going to be around 2^(10^27) if each atom could store 1 bit, so the time it takes to learn your opponent's Markov chain in real life is going to far exceed the lifetime of that human, or for that matter of the universe. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Iterated Prisoner Dilemma
by Warren Smith 08 Jul '12

08 Jul '12

On 7/8/12, Warren Smith <warren.wds(a)gmail.com> wrote: >> From: Ray Tayek <rtayek(a)ca.rr.com> >> Subject: [math-fun] ON "ITERATED PRISONER?S DILEMMA CONTAINS >> STRATEGIES THAT DOMINATE ANY EVOLUTIONARY OPPONENT" >> The highly technical paper, >> <http://www.pnas.org/content/early/2012/05/16/1206569109.abstract>" >> Prisoner?s Dilemma contains strategies that >> dominate any evolutionary opponent" by William H. >> Press and Freeman J. Dyson has now been published >> in PNAS (May 22, 2012), which was followed by a >> PNAS Commentary by Alexander Stewart and Joshua >> Plotkin of the Department of Biology, University >> of Pennsylvania > > --WDS: based on trying to figure out what they are doing without actually reading > it, > it seems they are arguing that if the opponent in IPD > generates his moves via a Markov chain... which presumably is > necessarily true for any real opponent given the laws of physics > since that opponent is bounded, i.e. has a finite bounded number of > states, and has access to a source of randomness, and hence must be a > Markov chain on those states... > then you, where by "you" I mean a Turing machine, > can outplay him asymptotically by learning his markov model and > then predicting his play. > > This is probably completely irrelevant to real life > because the "number of states" of a human being containing > 10^27 atoms is going to be around > 2^(10^27) > if each atom could store 1 bit, > so the time it takes to learn your opponent's Markov chain in real life > is going to far exceed the lifetime of that human, or for that matter of > the universe. --indeed, just to make this completely clear: suppose I play IPD by deciding my moves "defect" or "cooperate" by use of a pseudorandom number generator based on the AES (advanced encryption standard) using a secret key I selected once and for all by 256 coin tosses. How are Dyson and Press going to beat me? If they can it is equivalent to them breaking the AES cryptosystem. (Or put any other cryptosystem.) It is reasonable to suppose this is for practical purposes impossible in 1000 times the lifetime of this universe. This is true even though my strategy after the initial 256 coin tosses is completely deterministic, i.e. for Dyson and Press the simplest possible case. So this is all garbage: those evolutionary biologists writing the review acting like this all "matters" for biology, are completely confused. It should have no significance for biology at all. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Halting probability for Conway's Life
by Mike Stay 08 Jul '12

08 Jul '12

I figured out that the measure I wanted is this one: given a set of patterns where I'm told that the average area is <A>, the distribution on patterns that maximizes the entropy is the Gibbs distribution p(x) = exp(-s A(x)) / Z(s) where Z(s) = sum_x exp(-s A(x)) and s is such that sum_x A(x) p(x) = <A>. The partition function Z gives Chaitin's halting probability when the set of patterns x consists of those that evolve into a cyclic state and s = ln 2. It's clear that not all 2^A patterns of area A can be distinguished by bombarding them with gliders, etc. On the other hand, sliding block memory (http://www.radicaleye.com/lifepage/patterns/sbm/sbm.html) means that the area required to encode n bits is proportional to n. Are there better known bounds on the information encodable into a particular region? The fact that the area is proportional to n means that the halting probability of Life is at least partially random, i.e. given any universal prefix-free Turing machine U, there exists k ≥ 1 and c ≥ 0 such that the shortest program for U that computes the first n bits of the halting probability of Life is at least n/k - c bits long. -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

2 2

[math-fun] ON "ITERATED PRISONERS DILEMMA CONTAINS STRATEGIES THAT DOMINATE ANY EVOLUTIONARY OPPONENT"
by Ray Tayek 08 Jul '12

08 Jul '12

http://edge.org/conversation/on-iterated-prisoner-dilemma "Robert Axelrod's 1980 tournaments of iterated prisoner's dilemma strategies have been condensed into the slogan, Don't be too clever, don't be unfair. Press and Dyson have shown that cleverness and unfairness triumph after all." William Poundstone, from his Commentary Introduction In January I had the occasion to spend sometime in Munich with Freeman Dyson who informed me about a paper on "The Prisoner's Dilemma" he had co-authored with William H. Press, and he then briefly sketched out some of its ramifications. He indicated that they had come up with something new, a way to win the game. It's simple, he said. The winning strategy: go to lunch. And, he added, the only way to trump this strategy is to come up with a new theory of mind. I tried to go deeper but, he said, "I don't really understand game theory, I just did the math. This is really Bill Press's work." The highly technical paper, <http://www.pnas.org/content/early/2012/05/16/1206569109.abstract>"<http://www.pnas.org/content/early/2012/05/16/1206569109.abstract>Iterated Prisoners Dilemma contains strategies that dominate any evolutionary opponent" by William H. Press and Freeman J. Dyson has now been published in PNAS (May 22, 2012), which was followed by a PNAS Commentary by Alexander Stewart and Joshua Plotkin of the Department of Biology, University of Pennsylvania, entitled <http://www.pnas.org/content/early/2012/XXX>"<http://nr.com/whp/StewartPlotkinExtortion2012.pdf>Extortion and cooperation in the Prisoners Dilemma"<http://nr.com/whp/StewartPlotkinExtortion2012.pdf> (June 18, 2012). Here's the Abstract of the paper: "The two-player Iterated Prisoners Dilemma game is a model for both sentient and evolutionary behaviors, especially including the emergence of cooperation. It is generally assumed that there exists no simple ultimatum strategy whereby one player can enforce a unilateral claim to an unfair share of rewards. Here, we show that such strategies unexpectedly do exist. In particular, a player X who is witting of these strategies can (i) deterministically set her opponent Ys score, independently of his strategy or response, or (ii) enforce an extortionate linear relation between her and his scores. Against such a player, an evolutionary players best response is to accede to the extortion. Only a player with a theory of mind about his opponent can do better, in which case Iterated Prisoners Dilemma is an Ultimatum Game." Edge asked William Poundstone, author of the book The Prisoner's Dilemma, to explain the paper in non-technical terms. In his Commentary below, he writes: "Robert Axelrod's 1980 tournaments of iterated prisoner's dilemma strategies have been condensed into the slogan, Don't be too clever, don't be unfair. Press and Dyson have shown that cleverness and unfairness triumph after all." Also below are responses by William Press to Poundstone and by Freeman Dyson to Stewart and Plotkin. To kick off a Reality Club conversation, mathematician Karl Sigmund at University of Vienna, and biological mathematician Martin Nowak of Harvard, two pioneers of evolutionary game theory, comment below. --- co-chair http://ocjug.org/

1 0

[math-fun] Covering the first n naturals
by Adam P. Goucher 06 Jul '12

06 Jul '12

Let 0 < d < 1 be a real number, and n be a positive integer. Let S be the set {1, 2, 3, ..., n}, and let T be a subset of S with cardinality CEIL[dn], where CEIL[] is the ceiling function. Does there exist D = f(d) such that S can be covered by D translated copies of T? If so, then we could D-colour S = {1, 2, 3, ..., n}, where each monochromatic subset is a translated copy of a subset of T. By van der Waerden's theorem, we have that (for sufficiently large n) there exists a monochromatic arithmetic progression of length k. This means that T (being a superset) must also contain such a monochromatic arithmetic progression, providing a proof of Szemeredi's theorem. Sincerely, Adam P. Goucher

1 0

[math-fun] dark matter really exists?
by Warren Smith 06 Jul '12

06 Jul '12

Dark matter filament found, scientists say Astrophysicists say they have discovered one strand of the long-elusive dark matter filaments, thought to connect galaxies and help shape the universe. That was the headline of this LA times article http://www.latimes.com/news/science/la-sci-dark-matter-filament-20120705,0,… http://www.nature.com/news/dark-matter-s-tendrils-revealed-1.10951 http://www.nature.com/nature/journal/vaop/ncurrent/full/nature11224.html The filament of dark matter connects two galaxies; it is 5.8*10^7 light years long and 3*10^6 light years in diameter. It has mass between (6.5 and 9.8)*10^13 solar masses. In contrast the Milky Way has 1.25*10^12 solar masses and is 10^5 light years in diameter. So for those who want to believe there is no such thing as dark matter, since really there is some other theory of gravity which explains the gravitational effects attributed to dark matter... this would seem to present a serious challenge? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Travelers through the dessert
by Victor Miller 06 Jul '12

06 Jul '12

After listening to Car Talk this weekend, I was inspired to create the following question: We have an inexhaustible supply of *travelers* each of whom can carry up to 1 day's worth of rations (we measure the distance in days of travel time). One of them, designated the pilgrim, wants to set off across the dessert from an oasis, aided by a cohort of n other travelers -- the helpers. Each of his helpers can travel a certain distance, transfer some of his rations to the remaining travelers (pilgrim plus remaining helpers) and turn back to the oasis (and thus needs to keep enough rations to allow him to get there). After the last helper leaves, the pilgrim keeps going. When he runs out of rations a magical genie appears and creates a new oasis for him. Let L[n] denote the longest distance (in days) that the pilgrim can travel using n helpers. It's clear that L[n] <= 2 since the last helper to leave can't be more than 1 day's distance away from the oasis. It seems intuitively clear that as n ---> infinity that L[n] ----> 2. Indeed one can work out a recursion for L[n] and solve for it explicitly. However, is there a simple, non-computational proof of this fact which doesn't involve solving for L[n]?

6 9