December 2011 - mathfun@mailman.xmission.com

[math-fun] Fwd: Chess game in current Sherlock Holmes movie
by Henry Baker 23 Dec '11

23 Dec '11

Here's Adam Raoof's reply. Yes, Adam did provide a real game for this movie. I hope he got paid more than a few hundred bucks! A fitting tribute to Larsen, who died last year (2010) in Sept. http://en.wikipedia.org/wiki/Bent_Larsen Petrosian resigns before the mate in the game referenced below. What are the missing moves that result in "discovered check and, incidentally, mate" ? (Web site requires Java.) >Date: Fri, 23 Dec 2011 19:29:56 +0000 >Subject: Re: [math-fun] Chess game in current Sherlock Holmes movie >From: Adam Raoof <adamraoof(a)gmail.com> >To: Henry Baker <hbaker1(a)pipeline.com> >Cc: Paul Reiners <paul.reiners(a)gmail.com>, Hans Havermann <gladhobo(a)teksavvy.com> > >OK Henry - this is the game it was based on > >http://www.chessgames.com/perl/chessgame?gid=1106678 > >mainly because Holmes was playing white in the original script and won >with a queen sacrifice - the variation I used is in the notes - and as >a tribute to Larsen. Moreover this is one of my favourite tournament >books, and it was played in the year of my birth! > >However very soon after deciding on this line, the script was changed >and Holmes was given the black pieces... so we just reversed the >position and lost a move. As they announced the moves in descriptive >it made no fundamental difference. I added the line about 'discovered >check and, incidentally, mate', which made it to the film and which >Robert Downey Junior thought was "&&**ing awesome"! > >Adam > >On 22 December 2011 18:02, Henry Baker <hbaker1(a)pipeline.com> wrote: >> Outstanding! >> >> We're looking forward to seeing the original game. >> >> Thanks! >> >> At 03:13 PM 12/21/2011, Adam Raoof wrote: >>>Thanks for asking Hans, Henry et al! Actually not much of the footage of the actual game we filmed survived the edit, but it was a famous Larsen game with reversed colours and using some variations - I will dig it out and send you the score on Friday when I get home! >>> >>>Sent from my iPod >>> >>>On 21 Dec 2011, at 21:38, Henry Baker <hbaker1(a)pipeline.com> wrote: >>> >>>> Adam Raoof's rating is 2127 !! I'm impressed. Perhaps we should simply ask him; I just cc'd him on this email. >>>> >>>> At 01:13 PM 12/21/2011, Paul Reiners wrote: >>>>> I haven't seen the movie, but I started a discussion here: >>>>> >>>>> http://www.chess.com/forum/view/general/sherlock-holmes-a-game-of-shadows >>>>> >>>>> One person said: >>>>> >>>>> the credits (on IMDB <http://www.imdb.com/name/nm4668958/>) have Adam >>>>> Raoof<http://ratings.fide.com/card.phtml?event=405230>(I assume that >>>>> is the same guy) listed a technical adviser for chess >>>>> >>>>> If the director didn't change things up to make it more interesting then I >>>>> would guess it was a real game. >>>>> >>>>> On Wed, Dec 21, 2011 at 11:53 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >>>>> >>>>>> I saw this movie yesterday. >>>>>> >>>>>> http://en.wikipedia.org/wiki/Sherlock_Holmes:_A_Game_of_Shadows >>>>>> >>>>>> Q: Is the chess game in the movie real? The characters call out their >>>>>> moves in usual notation, but the chess board isn't shown. >>>>>> >>>>>> For those of you chess nuts who can do chess in your heads, would this >>>>>> be a real game? >>>>>> >>>>>> I would imagine that after spending $125 million in making this movie, >>>>>> someone must have hired a chess person for a few hundred dollars to >>>>>> make the game real. >-- >Best wishes > >Adam Raoof > >ECF Director of Home Chess >President: Middlesex County Chess Association >FIDE International Organiser & Arbiter >328 Watford Way >Hendon, London NW4 4UY >Mailing list: send a blank email to adamraoof-subscribe(a)topica.com >http://www.goldersgreenchess.blogspot.com/ >Hendon Chess Club: http://www.hendonchessclub.com/ >Mobile: 07855 036 537

2 1

[math-fun] DLMF fungous inflection
by Bill Gosper 23 Dec '11

23 Dec '11

(This was too easy for the kids, but it feels good when you find the words an Authority missed.) See http://dlmf.nist.gov/22.3.F2.mag and http://dlmf.nist.gov/22.3.F3.mag "For cn⁡(x,k) the curve for k=1/sqrt2=0.70710⁢… is a boundary between the curves that have an inflection point in the interval 0≤x≤2⁢K(⁡k), and its translates, and those that do not;..." a) why don't they just say "at x=K(k)" vs "in the interval 0≤x≤2⁢K(⁡k)"? b) Huh? cn⁡(x,k) always has an inflection point there! But *something* happens at k=1/sqrt2. What should they have said? --rwg Caution: DLMF uses K(modulus) vs K(parameter), so if you plot this with Macsyma or Mma, the magic k = 1/2, not 1/sqrt2. In either case, K=4 (1/4)!^2/Sqrt[Pi] ~ 1.85407 (This K property is imperfectly analogous to the graphical definition of Halphen's constant, about 69% into http://gosper.org/thetpak.html .)

2 1

[math-fun] BBP functions, more careful look
by Warren Smith 23 Dec '11

23 Dec '11

BBP functions (Bailey-Borwein-Plouffe) =====Warren D Smith====Dec 2011=== I seem to have made another mistake (will be explained below). In this post, I will review "BBP functions" hopefully more carefully this time... BBP1: ln(3) = sum(n>=1) 16^(-n) * (16/(4*n-3) + 4/(4*n-1)) pi = sum(n>=0) (-4)^(-n) * (2/(4*n+1) + 1/(2*n+1) + 1/(4*n+3)) are examples of "BBP formulas." They enable computing the Nth digit of ln(3) in radix 16, or the Nth digit of pi in radix 4, WITHOUT computing the preceding N-1 digits... and the whole algorithm takes roughly O(N) operations using O(logN) bits of memory. This is essentially because there is a fast way [based on fast modular powering] to figure out the digits in the vicinity of the Nth in the decimal (actually radix=R) expansion of any rational number p/q with p,q small. BBP2: Simon Plouffe pointed out that he invented a weaker kind of BBP-like formula which then got explored & improved further by Fabrice Bellard & Xavier Gourdon: http://arxiv.org/abs/0912.0303 http://bellard.org/pi/pi_n2/pi_n2.html http://numbers.computation.free.fr/Constants/Algorithms/nthdecimaldigit.pdf Examples of this kind of formula are pi+3 = sum(n>=1) n * 2^n / binomial(2*n, n) zeta(3) = (5/2) * sum(n>=1) (-1)^(n-1) / (n^3 * binomial(2*n, n)). In these formulas, the rational numbers p/q involved have LARGE q, but this is ok because q is factorable into small primes with no large powers of a prime, which allows the whole rational p/q can be rewritten as a sum of rationals with small denominators. As a result, these authors showed how to evaluate the Nth digit of pi+3 now in ANY fixed radix in roughly O(N^2) time using O(logN)^2 bits of memory. The BBP2 formulas are of less interest than BBP1 because they actually run much SLOWER to compute the Nth digit than algorithms which compute ALL digits 1,2,...,N. (You could argue they still have some interest because of their tiny memory needs and since they now work in every radix...) BBP3: Another weaker kind of BBP formula would be exemplified by F(x) = -ln(1-x)/(x*(1-x)) = sum(n>=0) H[n+1] * x^n where H[n] = 1 + 1/2 + 1/3 + ... + 1/n is the nth "Harmonic number." By regarding the series as a DOUBLE sum we can compute the Nth decimal digit of F(1/10) in roughly O(N^2) operations and memory O(logN). Similarly one could consider triple sums, etc; then we would evaluate the Nth digit in polynomial time O(N^S) operations roughly, and O(logN) bits of memory, for an S-fold sum for any fixed S. Again, I consider these BBP3 formulas of less interest than BBP1. However, in at least some cases I think you can "cheat" to evaluate the Nth digits of these things effectively with a smaller value of S, i.e. faster runtime than the naive bound. If so, in such cases they would regain interest, so it would be good to figure out just when this happens. BBP4: I also pointed out to Plouffe that if you are willing to consume "quasipolynomial" compute time N^O(D) where D can now depend logarithmically on N -- or even worse like a power of log(N) -- then you can compute the Nth digit of a much wider class of reals using log(N)^O(1) bits of memory. This works in any radix and for a far larger class of real numbers. I consider this result to be of even less interest than BBP2 and BBP3 because it is even slower. Nevertheless (since Simon Plouffe told me he did not believe me), I will explain how this is done. Let X be ANY real number which is "D(N)-shallow" meaning it can be computed to N-digit accuracy starting from 0 and 1 by an D(N)-depth "arithmetic circuit" each of whose nodes adds, subtracts, or multiplies its two inputs and outputs the result. There are also certain other operations nodes could use, such as, the nodes could only look at certain subranges of the digits of their inputs, or could keep track of the number of digits the number has if it is an integer (these go beyond the 3 arithmetic operations strictly speaking, but still would be allowed). Then I claim the Nth digit of X can be computed by an algorithm taking roughly N^D(N) time and running in O(D(N)*logN) bits of memory. The method is simple. To compute the Nth digit of X -- actually a O(logN)-wide block of digits starting at position N, and we shall assume no "carries" propagate further than distance O(logN), an assumption which the previous BBP algorithms also needed to make: * if X=A+B then compute the digit blocks for A and B and add them. * If X=A-B ditto. * If X=A*B then simply scan over k computing the kth digit of A and the (N-k)th digit of B, recursively, and accumulate products. The recursion "stack" gets to be O(D(N))-deep and each recursion level you need to keep track of a counter (we called it k) using O(logN) bits of memory. Example: e=1+1/2!+1/3!+... We can compute the Nth digit of e in O(logN)^2 bits of memory and time N^O(logN) as follows. We need to show that e can be computed to N-digit accuracy by an O(logN)-deep arithmetic circuit. The divisions will be computed using +, -, * only via Newton iteration in O(logN) depth to get N digit accuracy. The sum with N terms will be computed in only O(logN) depth using binary-tree summation. The factorials will be computed in only O(logN) depth by using * if N odd: N! = N * (N-1)! * if N even: N! = (N/2)!^2 * binomial(N,N/2) and get digits of binomial(N,N/2) inside high powers by using Newton binomial formula and using binary powering of integers like 1000001^N [these numbers will be O(N^2) digits long but at we shall only employ at O(N)-long subranges of them; but even using the full length would be fine]. QED. Further examples: A. Every hypergeometric function value pFq([a1,a2,...,ap],[b1,b2,...,bq]; x) where x=1/radix or x=integer and q>p (or q=p for x=1/radix) is O(logN)-shallow. B. For general integer a,b every hypergeometric function value pFq([a1,a2,...,ap],[b1,b2,...,bq]; a/b) is O(logN)^2-shallow. C. Any rational power (a/b)^(p/q) of a rational, or any algebraic number, is O(logN)-shallow. D. Composing functions basically adds their depths. LARGE CLASSES OF FUNCTIONS THAT ARE BBP: I. If R(x) is any rational function of x with integer coefficients and whose poles lie on the unit circle |x|=1, then R(x) is BBP1 whenever x=1/radix. Proof sketch: expand R(x) using partial fractions, find the Maclaurin series for each term, and note its coefficients of x^n are rational(n). Also if R(x) has poles on circles |x|=r where r is a power of the radix, this also is ok -- but that specializes things to a particular radix, whereas with r=1 only, R(x) will preserve BBPness for general radix. II. Integration: integral F(x) dx is BBP1 if F was. Proof sketch: c[n]*x^n in the Maclaurin series becomes c[n]*x^(n+1)/(n+1). III. Derivative: F'(x) is BBP1 if F was. IV. Sum: (a/b)*F(x)+(c/d)*G(x) is BBP1 if F and G are and a,b,c,d are integers. V. Product: F(x)*G(x) is BBP3 if F and G were BBP1 or BBP3. Note there is a weakening here: we fall into the weaker BBP-like function class BBP3 not the most interesting class BBP1. (That was my error before.) VI. Powers of argument: F(x^Q) is BBP1 if Q is positive integer and F is BBP1. In the above it is ok to replace all "BBP1" by "BBP3." By performing operations II, III, IV, V, VI starting from functions in I we get a very large set of BBP3 functions F(x). If x=a/b is rational where b is a power of the radix, then the Nth digit of F(x) can be computed in polynomial time with O(logN) bits of memory. I think (but have not carefully checked) that every BBP formula so far compiled in Bailey's huge compendium, lies within a tiny subclass of the above. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Erich Friedman's game
by Warren Smith 23 Dec '11

23 Dec '11

RCS: > But Erich's version has complications that make it > more challenging. First is the finiteness, and our goal > is not to maximize our expected point total, but our chance > of surmounting the three-point threshold. Second is the > chance for both players to alter their play based on the > state of the game so far. --indeed. It would be possible to solve the game by working backwards from the end state, using the result of the game-solve at the penultimate stage as the payoffs for the game 1 stage earlier, then solve that game, and so on. This is kind of in miniature the sort of problem faced by those building computerized poker players.

2 1

Re: [math-fun] Shrine problem
by Dan Asimov 23 Dec '11

23 Dec '11

Andy wrote: << On Thu, Dec 22, 2011 at 2:26 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: << The "shrine problem" is, given a family S of shapes (let's say certain subsets of R^n) for which it makes sense to talk about a continuous curve [0,1] -> P, >> This requires not just a "family" S, but a "topological space" S. In the cases below, you specify the set S, but not the intended topology on S. It's not at all clear to me what the intended topology is on, say, the set of embedded arcs in the plane. Are you considering them just as subsets of the plane, or as parameterized arcs, so that two parameterizations of the same arc are considered different points of S? Assuming the latter for the moment, at least two topologies occur to me that seem natural; the topology of pointwise convergence and the topology of uniform convergence. Which is intended in the problem? >> The set of shapes S doesn't need to have a topological structure in order to define a continuous curve in S. A continuous curve (sheesh, I keep screwing up the notation! Bleeeh) in say the set S of embedded arcs in R^2 could just be defined by the natural condition that: Given any continuous map F: I x [0,1] -> R^2 (where I := [0,1]also) such that the restriction of F to any I x {t} is an embedding, we will say that s: [0,1] -> S via s(t) := F(I x {t}) is a continuous curve in S. << << c_n) S := all smooth Riemannian metrics on the n-disk D^n. (In this case, maps into R^n above must be replaced with maps into D^n.) These problems have a curious status: >> I'm confused; a smooth Riemannian metric on D^n is not a subset of D^n. So I don't know how to make sense of the requirement that P(s) is a member of s. P(s) is a point in D^n; S is a smooth Riemannian metric on D^n. >> That's the reason for the parenthetical sentence "In this case . . .." Here we need only that P: S -> D^n (subject to the 1) continuity condition and the 2) equivariance with respect to isometries f: D^n -> D^n between two (possibly identical) Riemannian structures on D^n. --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Shrine problem
by Dan Asimov 23 Dec '11

23 Dec '11

The "shrine problem" is, given a family S of shapes (let's say certain subsets of R^n) for which it makes sense to talk about a continuous curve [0,1] -> F, find a selection function P: S -> R^n such that for all s in S, P(s) is a member of s. P must also satisfy two conditions: 1) Given a continuous curve of shapes s:[0,1] -> S, the map [0,1] -> R^n given by t |-> P(s_t) is continuous, and 2) If some isometry I: R^n -> R^n carries one shape s_1 of S onto another one s_2, then P(s_2) = I(P(s_1)). --------------------------------------------------------------------------------------------------- Case in point: a) All embedded closed arcs in the plane. If we cared only about rectifiable arcs, this would be easy: Let P(A) be its midpoint. But the problem is to find a P for all embedded arcs, rectifiable or not. Finally, (15+ years after first working on this) I think I've finally solved this problem. Hallelujah! Some other cases of the problem: b_n) S := all n-disks smoothly embedded in R^n I've recently solved this with a method that's much simpler than for case a). c_n) S := all smooth Riemannian metrics on the n-disk D^n. (In this case, maps into R^n above must be replaced with maps into D^n.) These problems have a curious status: n = 1: Just take the midpoint. n = 2: A bit tricky, but doable. n = 3: A non-constructive proof (based on a theorem of Allen Hatcher) shows a solution exists, but no explicit definition of the selection function P is known. n = 4: Unknown. n = 5: Unknown. n >= 6: No solution is possible. --Dan ________________________________________________________________________________________ It goes without saying that .

2 1

[math-fun] Erich Friedman's game
by Warren Smith 23 Dec '11

23 Dec '11

Erich Friedman: each round i secretly write down either the number 1 or 2, and you guess which. if you guess correctly, you get that many points. otherwise you get 0 points that round. after 4 rounds, you win if your total is 3 or more points. otherwise i win. who is favored, you or me? both players know the result of each round after it is over, and before the next round begins. --a simpler game has an infinite number of rounds (or just one) and goal is to maximize total points per round. Optimum strategy in simpler game is "you" guess "1" with probability P and "2" with probabiilty=(1-P) "I" provide "1" with probability A and "2" with prob=1-A Expected payoff for "you" = P*1*A + (1-P)*2*(1-A) optimum parameter choices: A=P=2/3 payoff with those choices = 6/9 = 2/3 point per round. (sorry to be boring...) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] a game
by Erich Friedman 22 Dec '11

22 Dec '11

let's play a game. each round i secretly write down either the number 1 or 2, and you guess which. if you guess correctly, you get that many points. otherwise you get 0 points that round. after 4 rounds, you win if your total is 3 or more points. otherwise i win. who is favored, you or me? a not-so-useful hint that will let you check your work: your probability of winning (when written as a fraction in lowest form) has denominator 4069. erich

2 3

Re: [math-fun] Shrine problem
by Dan Asimov 22 Dec '11

22 Dec '11

Editing problem correction: "F" in the first sentence should read "S". Sorry about that. (Also note that s_1 = s_2 is not excluded.) --Dan << The "shrine problem" is, given a family S of shapes (let's say certain subsets of R^n) for which it makes sense to talk about a continuous curve [0,1] -> F, find a selection function P: S -> R^n such that for all s in S, P(s) is a member of s. P must also satisfy two conditions: 1) Given a continuous curve of shapes s:[0,1] -> S, the map [0,1] -> R^n given by t |-> P(s_t) is continuous, and 2) If some isometry I: R^n -> R^n carries one shape s_1 of S onto another one s_2, then P(s_2) = I(P(s_1)). >> ________________________________________________________________________________________ It goes without saying that .

1 0

Re: [math-fun] BBP functions (Bailey-Borwein-Plouffe)
by Warren Smith 22 Dec '11

22 Dec '11

DHB: Could you provide some details? Why do you say the functions are in the BBP class? WDS: My aim was to make the coefficient of x^n in their Maclaurin series be a rational function of n with integer coefficients. Such functions are in BBP class. Unless I screwed up, this ought to be provable inductively and I thought was pretty obvious? Ummm. Oh dear. Actually, I think I *did* screw up: when I said "rational-fn linear combinations" I should have demanded that all the rational functions of x we use need to be chosen so their poles (if any) all are located on the perimeter of the unit circle (which they were in my first definition). You want coeff[n] to be rational(n) -- not to also have exponential(n) dependence, which would happen if poles located on other-radius circles. By the way,I just thought of a slight further extension: if F(x) is in BBP class, then so is F(x^Q) for any positive integer Q (since a number written in radix 1000 is also a number written in radix 10) and we can put this into the inductive definition too.

1 0