May 2014 - mathfun@mailman.xmission.com

[math-fun] Atropa Belladonna
by Fred Lunnon 05 Jun '14

05 Jun '14

How to destroy any ability at chess which you may previously have enjoyed. Playing from the centre of an infinite open board --- Q1. Prove that Every point has some knight-move neighbour at smaller knight-move distance from the origin if and only if Every point has some knight-move neighbour at greater knight-move distance from the origin. Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps. Q3. Denote e(x, y) the number of shortest knight paths from (0,0) to (x,y) . Prove that e(1999999999, 3) = e(1500000000, 1499999998) . Fred Lunnon

4 21

Re: [math-fun] General way to avoid mispredicted branches (in sorting, & probably many other tasks)
by Henry Baker 04 Jun '14

04 Jun '14

In computer architectures, branch prediction "works" only to the extent that the probability of one arm is substantially smaller than the other arm. If both arms are equally likely, then many/(most?) branch prediction schemes will actually do worse, since the overheads for the branch prediction scheme aren't paid for on either arm. The best sorting algorithms arrange for the comparisons to be "most informative" -- i.e., their branch probabilities are very close to 1/2 -- so traditional "branch prediction" isn't going to be very helpful. Now to the extent that you can defer branches and deal with the consequences later may allow you to overlap some activity so that previously sequential operations are now in parallel. However, you should be aware that for most modern CPU's, things like "instruction fetch" are more-or-less free, since instruction fetch units typically fetch instructions from both branch paths. At 04:58 PM 5/20/2014, Warren D Smith wrote: >Suppose you are doing quicksort. >Zoing, zoing, zoing, you do compares, and suddenly you decide >"aha! this last comparison tells me I need to swap item[K]!" >And then you branch off someplace else in your program to do it. >Big lose. Mispredicted branch.

3 2

[math-fun] David Wilson's 1-dimensional gun in Ponder This
by Michael Kleber 03 Jun '14

03 Jun '14

Hey Funsters, Oded Margalit's "Ponder This" puzzle this month is a bit about the "1-Dimensional Gun" model that David Wilson introduced here in June 2012. I told Oded about it when we were both speaking at the ITA workship in San Diego in February. http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/May2014.html The question Oded asked: "Every second, a gun shoots a bullet in the same direction at a random constant speed between 0 and 1. The speeds of the bullets are independent uniform random variables. Each bullet keeps the exact same speed and when two bullets collide, they are both annihilated. After shooting 20 bullets, what is the probability that eventually all the bullets will be annihilated?" Oded has a closed form for the probability of all bullets being annihilated when you shoot 2n of them, but not, I think, the probability of 2k>0 surviving. --Michael -- Forewarned is worth an octopus in the bush.

1 1

[math-fun] Data compressing the primes < 104000
by Bill Gosper 01 Jun '14

01 Jun '14

with CarmichaelQ (fairly simple), and three special cases, Block[{a = 15485857, b = 29462131}, Reap[Do[If[! PrimeQ[k] && ! CarmichaelQ[k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 117568}]]] {Null, {{56033, 73633, 93961, 104653}}} There may well be superior and smaller a and b. And almost certainly superior larger ones. But I don't have a good way to look for them. --rwg

1 2

[math-fun] algebraic geometry query
by Fred Lunnon 01 Jun '14

01 Jun '14

Given a plane curve C defined by f = 0 with f(x, y) polynomial, and a region R of the plane (possibly extending to infinity), I assert that C avoids R provided C avoids the boundary of R ; and C has no critical points within R . There must be a well-known theorem to this effect (unless, of course, it's actually false --- a situation by no means previously unknown). But I don't know a reference (or a counter-example) --- anybody? A straightforward way to locate the critical points seems to be to compute the discriminant g of f with respect to (say) x , then find the roots of g(y) = 0 . Is there a more respectable alternative? WFL

5 21

[math-fun] critical points curves regions
by Warren D Smith 01 Jun '14

01 Jun '14

Andy Latto: I think this is really a theorem of differential geometry, not of algebraic geometry; the only place Warren's proof uses the fact that f is polynomial is when he needs it to be sufficiently smooth. --WDS: not so. I also used the fact the zero set of a polynomial, restricted to a compact region, has finite measure, e.g. cannot be an infinite spiral. One can easily construct an INFINITELY differentiable (i.e way smooth) function f(x,y) such that f(x,y)=0 is a spiral curve that within some annulus -- or disc -- makes an infinite number of winds. The function f will be 0 on the spiral, and in between windings will have a ridge or valley, but the ridge always has a slight slope, approaching but never quite becoming horizontal. As a result there are no critical points of f within the annulus. > Since we can replace R by any smaller simply connected region that > doesn't touch C, we may as well choose R to be diffeomorphic to a > disc, and the theorem then becomes: > > For any sufficiently smooth (C2?) function f on the unit disc, if f is > nonzero on the unit circle, but has zeroes inside the disc, then it > has a critical point inside the disc. > > Proof: if f is negative on the unit circle, its maximum is a critical > point; if f is positive on the circle, its minimum is a critical > point. --a counterexample to that "theorem" and "proof" is the function f(x,y)=x? Oh, by "nonzero" you meant "never zero." Aha. Right, this is now trivial. > This works in any dimension, and we don't really need the > Perelman-Thurston classification theorem, the Jordan Curve theorem, or > the classification of surfaces. Latto: All we need is the fact that the boundary of a compact simply connected set is connected; the theorem doesn't really require that R is simply connected, merely that it has connected boundary. WDS: my infinite spiral counterexample seems to indicate that is false (within a 3D solid torus)? Well, I think the final last winding of the spiral, which never comes, is a circular ring of critical points, which lie on the boundary of the region, but not inside it, and thus technically yield a counterexample, at least to some wordings of the theorem.

2 1

[math-fun] 10 billion constants
by Simon Plouffe 31 May '14

31 May '14

Hello, I made possible the access of all the inverter files on my site at : http://www.plouffe.fr/ipgz/ this is a first draft , the files there are compressed with gzip and can be decompressed with 7-zip or equivalent program on a pc. Beware : there are 501 gigabytes of data. http://www.plouffe.fr/ip/ is a uncompressed version, being filled right now, it will take a couple of days before everything is there. ps : have fun. Simon Plouffe

1 0

[math-fun] Playing with some spaces on Khan Academy
by Mike Stay 31 May '14

31 May '14

Here are a few little programs I wrote up on Khan Academy's "learn to program in JavaScript" site that let you draw on a plane by left-clicking and then translate it by right-clicking. The planes are the real projective plane, the Poincare disk, and the Klein-Beltrami disk, respectively: https://www.khanacademy.org/cs/rp/6016720262135808 https://www.khanacademy.org/cs/hyperbolic-poincar-disk/6049095859830784 https://www.khanacademy.org/cs/hyperbolic-beltrami-klein-disk/5089362388189… -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

1 0

Re: [math-fun] Fractal nomenclature question
by Bill Gosper 31 May '14

31 May '14

Jim's suggestion of a Clouseauian "sneauflec" is cute. The French word for flake is "flocon". (As in snowflake = flocon de neige.) --Dan On May 30, 2014, at 6:47 PM, Bill Gosper <billgosper(a)gmail.com> wrote: On 2014-05-30 18:23, Dan Asimov wrote: |. . . Finally, define the fractal G := bd(H_oo), the boundary of H_oo. It has the lovely property that a rosette of 7 translated copies of it fitting snugly together forms a magnified and rotate copy of H_oo, as the regular hexagon doesn't quite do. It's easy to see the Hausdorff measure d of G is the solution to sqrt(7)^d = 3, so d = log_7(9) = 1.1291500681.... Reminder: http://gosper.org/wikifrac.gif Very nice! I'd forgotten about those animations. QUESTION: Does G have an official name? --Dan I'm satisfied (≠ thrilled) with Franceflake. --rwg More to your point, Francecoast or France boundary. But these sound too much like French toast and French Laundry. --rwg

3 2

[math-fun] curves and critical points -- proof of corrected conjecture
by Warren D Smith 31 May '14

31 May '14

So the current repaired conjecture is, or anyhow I presume should be, this: CONJECTURE: Given a plane curve C defined by f = 0 with f(x, y) polynomial, and a simply-connected compact region R of the plane with connected interior C avoids R provided 1. C avoids the boundary of R, and 2. f(x,y) has no critical points (meaning grad f = 0) within R. HERE'S MY PROOF: The only way C can fail to avoid R is (i) C hits boundary(R). But that case is already handled in the theorem statement. (ii) A connected component CC of C lies entirely within R's interior. >From now on we only consider case (ii) since that is all we need to consider. Note that any self-crossing points, or isolated points, or end-points of the curve automatically are critical points. (Actually I do not think end-points are possible, but their possibility or impossibility will not matter.) Hence wlog we need only consider the case where CC has no self-crossing or isolated or end points. Since CC is by assumption entirely contained in a compact region with no endpoints and no crossing points (and it s not just an isolated point) it necessarily either closes on itself, or spirals forever, but the latter option is impossible because f is a finite-degree polynomial. So CC is a closed compact curve of the same topological type as a circle. Now such a CC necessarily contains a critical point of f(x,y) inside it, because f(x,y)=0 on the closed circle-like curve CC and is (wlog) >0 everytwhere that is infinitesimally inside it, and is continuous and differentiable, hence must have a maximum on the compact region inside CC, which necessarily is >0, and which necessarily is a critical point. Q.E.D. GENERALIZATIONS: It seems to me this conjecture ought to be true not only for algebraic curves in the xy plane, but also for algebraic (D-1)-dimensional surfaces in D-dimensional space. Anyhow when D=3. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 7