June 2012 - mathfun@mailman.xmission.com

Re: [math-fun] Wilson's 1D gun problem
by Adam P. Goucher 11 Jun '12

11 Jun '12

> --the details in this proof seem to me to be a bit vague. > But I think he is right. I think a simpler proof is the next n shots > all use exactly > the maximum allowed speed. This kills the previous n bullets assuming > none used exactly max speed. The bullet speeds are in the open interval (0,1), if I understood the problem correctly, so there is no maximum speed and we can fire bullets at 1-epsilon. Sincerely, Adam P. Goucher

1 0

Re: [math-fun] Gun problem: more simulation results
by W. Edwin Clark 09 Jun '12

09 Jun '12

I mentioned David's gun problem to my friend Brent Meeker (appropriately a rocket scientist). Brent wrote a simulation and obtained some interesting graphs which can be found at http://brentmeeker.com/?page_id=48 ---Edwin Clark

1 0

[math-fun] Gun problem
by David Wilson 09 Jun '12

09 Jun '12

A gun sits on a line. Every second, the gun shoots a bullet to the right at a random constant speed between 0 and 1. If two bullets collide they annihilate. It's probability 0, but if more than two bullets collide, the slowest bullets annihilate in pairs. Can we expect the speed of the furthest bullet to approach 1 over time?

3 3

[math-fun] Kimberling's polynomial problem
by Bill Gosper 09 Jun '12

09 Jun '12

(The GF of the elementwise product of two (constant coeff) linear recurrences.) ClarkK>It appears that a denominator may be a polynomial whose roots are the>reciprocal-products 1/(r(i)*s(j)), where r(i) ranges through all the>roots of q(x) and s(j) ranges through all the roots of v(x).>Clark Kimberling WDS>--This polynomial A(x) is expressible in terms of the original polynomials q(x) and v(x) by the use of "resultant" -- you can evaluate using determinants without computing any roots, just do rational operations. Specifically, the polynomial B(x) whose roots are the products r(i)*s(j) should be B(x) = Resultant_y [q(y), y^degree(v) * v(x/y)] and then A(x) is the "reverse" of B(x) to reciprocate its roots, A(x) = B(1/x) * x^degree(B). The "numerator" polynomial Kimberling also wanted could then be obtained by simply solving for it by given the known values of the first degree # of outputs, i.e. series coefficients, of the generating function. This is just a polynomial multiplication. ------- Now suppose NONconstant coeffs, but we'll settle for the recurrence relation of the elementwise product of two sequences, given their separate recurrences. E.g., the HolonomicFunctions package by Christoph Koutschan, RISC-Linz, Version 1.4.2 (08.02.2011) gives the 2nd order recurrence for incomplete Gamma: In[71]:= Annihilator[Gamma[a, z], S[a]] Out[71]= {Subscript[S, a]^2 + (-1 - a - z)*Subscript[S, a] + a*z} (S is the shift operator). Now how the heck does it get In[72]:= Annihilator[Gamma[a, z]^2, S[a]] Out[72]= {(1 + a + z)* Subscript[S, a]^3 + (-4 - 8*a - 5*a^2 - a^3 - 6*z - 7*a*z - 2*a^2*z - 4*z^2 - 2*a*z^2 - z^3)*Subscript[S, a]^2 + (2*z + 7*a*z + 9*a^2*z + 5*a^3*z + a^4*z + 4*z^2 + 10*a*z^2 + 8*a^2*z^2 + 2*a^3*z^2 + 3*z^3 + 5*a*z^3 + 2*a^2*z^3 + z^4 + a*z^4)* Subscript[S, a] + (-2*a^2*z^3 - 3*a^3*z^3 - a^4*z^3 - a^2*z^4 - a^3*z^4)} ? Worse: In[73]:= Annihilator[Gamma[a, z]*Gamma[a, y], S[a]] Out[73]= {(2 + 3*a + a^2 - y*z)*Subscript[S, a]^4 + (-18 - 39*a - 29*a^2 - 9*a^3 - a^4 - 6*y - 11*a*y - 6*a^2*y - a^3*y - 6*z - 11*a*z - 6*a^2*z - a^3*z + 3*y*z + a*y*z + 3*y^2*z + a*y^2*z + 3*y*z^2 + a*y*z^2 + y^2*z^2)*Subscript[S, a]^3 + (24*y + 68*a*y + 74*a^2*y + 39*a^3*y + 10*a^4*y + a^5*y + 24*z + 68*a*z + 74*a^2*z + 39*a^3*z + 10*a^4*z + a^5*z + 36*y*z + 72*a*y*z + 53*a^2*y*z + 17*a^3*y*z + 2*a^4*y*z - 10*y^2*z^2 - 9*a*y^2*z^2 - 2*a^2*y^2*z^2 - 2*y^3*z^2 - a*y^3*z^2 - 2*y^2*z^3 - a*y^2*z^3)*Subscript[S, a]^2 + (-12*y*z - 52*a*y*z - 91*a^2*y*z - 82*a^3*y*z - 40*a^4*y*z - 10*a^5*y*z - a^6*y*z - 12*y^2*z - 40*a*y^2*z - 51*a^2*y^2*z - 31*a^3*y^2*z - 9*a^4*y^2*z - a^5*y^2*z - 12*y*z^2 - 40*a*y*z^2 - 51*a^2*y*z^2 - 31*a^3*y*z^2 - 9*a^4*y*z^2 - a^5*y*z^2 - 6*y^2*z^2 - 11*a*y^2*z^2 - 6*a^2*y^2*z^2 - a^3*y^2*z^2 + 2*y^3*z^2 + 5*a*y^3*z^2 + 4*a^2*y^3*z^2 + a^3*y^3*z^2 + 2*y^2*z^3 + 5*a*y^2*z^3 + 4*a^2*y^2*z^3 + a^3*y^2*z^3 + 2*y^3*z^3 + 3*a*y^3*z^3 + a^2*y^3*z^3)* Subscript[S, a] + (12*a^2*y^2*z^2 + 28*a^3*y^2*z^2 + 23*a^4*y^2*z^2 + 8*a^5*y^2*z^2 + a^6*y^2*z^2 - 2*a^2*y^3*z^3 - 3*a^3*y^3*z^3 - a^4*y^3*z^3)} Worse: In[74]:= Annihilator[Gamma[a, z]*Gamma[a + b, z], S[a]] Out[74]= {(1 + 2*a + a^2 + b + a*b - z - z^2)*Subscript[S, a]^4 + (-9 - 24*a - 22*a^2 - 8*a^3 - a^4 - 12*b - 22*a*b - 12*a^2*b - 2*a^3*b - 3*b^2 - 4*a*b^2 - a^2*b^2 + 4*z - 6*a*z - 8*a^2*z - 2*a^3*z - 3*b*z - 8*a*b*z - 3*a^2*b*z - b^2*z - a*b^2*z + 10*z^2 + 4*a*z^2 + 2*b*z^2 + 6*z^3 + 2*a*z^3 + b*z^3 + z^4)* Subscript[S, a]^3 + (20*z + 68*a*z + 89*a^2*z + 56*a^3*z + 17*a^4*z + 2*a^5*z + 34*b*z + 89*a*b*z + 84*a^2*b*z + 34*a^3*b*z + 5*a^4*b*z + 16*b^2*z + 32*a*b^2*z + 20*a^2*b^2*z + 4*a^3*b^2*z + 2*b^3*z + 3*a*b^3*z + a^2*b^3*z + 16*a*z^2 + 24*a^2*z^2 + 12*a^3*z^2 + 2*a^4*z^2 + 8*b*z^2 + 24*a*b*z^2 + 18*a^2*b*z^2 + 4*a^3*b*z^2 + 4*b^2*z^2 + 6*a*b^2*z^2 + 2*a^2*b^2*z^2 - 16*z^3 - 16*a*z^3 - 4*a^2*z^3 - 8*b*z^3 - 4*a*b*z^3 - 11*z^4 - 10*a*z^4 - 2*a^2*z^4 - 5*b*z^4 - 2*a*b*z^4 - 3*z^5 - 2*a*z^5 - b*z^5)* Subscript[S, a]^2 + (-4*z^2 - 20*a*z^2 - 41*a^2*z^2 - 44*a^3*z^2 - 26*a^4*z^2 - 8*a^5*z^2 - a^6*z^2 - 10*b*z^2 - 41*a*b*z^2 - 66*a^2*b*z^2 - 52*a^3*b*z^2 - 20*a^4*b*z^2 - 3*a^5*b*z^2 - 8*b^2*z^2 - 26*a*b^2*z^2 - 31*a^2*b^2*z^2 - 16*a^3*b^2*z^2 - 3*a^4*b^2*z^2 - 2*b^3*z^2 - 5*a*b^3*z^2 - 4*a^2*b^3*z^2 - a^3*b^3*z^2 - 8*z^3 - 32*a*z^3 - 50*a^2*z^3 - 38*a^3*z^3 - 14*a^4*z^3 - 2*a^5*z^3 - 16*b*z^3 - 50*a*b*z^3 - 57*a^2*b*z^3 - 28*a^3*b*z^3 - 5*a^4*b*z^3 - 10*b^2*z^3 - 23*a*b^2*z^3 - 17*a^2*b^2*z^3 - 4*a^3*b^2*z^3 - 2*b^3*z^3 - 3*a*b^3*z^3 - a^2*b^3*z^3 + 3*z^4 + 8*a*z^4 + 7*a^2*z^4 + 2*a^3*z^4 + 4*b*z^4 + 7*a*b*z^4 + 3*a^2*b*z^4 + b^2*z^4 + a*b^2*z^4 + 4*z^5 + 10*a*z^5 + 8*a^2*z^5 + 2*a^3*z^5 + 5*b*z^5 + 8*a*b*z^5 + 3*a^2*b*z^5 + b^2*z^5 + a*b^2*z^5 + z^6 + 2*a*z^6 + a^2*z^6 + b*z^6 + a*b*z^6)*Subscript[S, a] + (4*a^2*z^4 + 12*a^3*z^4 + 13*a^4*z^4 + 6*a^5*z^4 + a^6*z^4 + 4*a*b*z^4 + 18*a^2*b*z^4 + 26*a^3*b*z^4 + 15*a^4*b*z^4 + 3*a^5*b*z^4 + 6*a*b^2*z^4 + 15*a^2*b^2*z^4 + 12*a^3*b^2*z^4 + 3*a^4*b^2*z^4 + 2*a*b^3*z^4 + 3*a^2*b^3*z^4 + a^3*b^3*z^4 - a^2*z^5 - 2*a^3*z^5 - a^4*z^5 - a*b*z^5 - 3*a^2*b*z^5 - 2*a^3*b*z^5 - a*b^2*z^5 - a^2*b^2*z^5 - a^2*z^6 - 2*a^3*z^6 - a^4*z^6 - a*b*z^6 - 3*a^2*b*z^6 - 2*a^3*b*z^6 - a*b^2*z^6 - a^2*b^2*z^6)} In[75]:= Annihilator[Gamma[a, z]*Gamma[a + b, y], S[a]] You don't want to know! --rwg

1 0

[math-fun] The hot spots conjecture (statement of & a few remarks on)
by Warren Smith 09 Jun '12

09 Jun '12

>From http://michaelnielsen.org/polymath1/index.php?title=The_hot_spots_conjecture and other sources: The hotspots conjecture can be expressed in simple English as: Suppose a flat piece of metal, represented by a two-dimensional bounded connected domain R, is given a generic initial heat distribution which then flows throughout the metal. Assuming the metal is insulated (i.e. no heat escapes from the piece of metal), then at all sufficiently large times, the hottest and coldest points on the metal both will lie on its boundary... Equivalently, the 2nd eigenfunction of the laplacian has its global max and global min on the boundary of the domain. This conjecture has been proven for some domains and disproven for others. It is conjectured by Rodrigo Banuelos for any bounded simply-connected planar domain. It is false for certain bounded planar domains with 2 holes. The polymath7 project is to prove it for acute triangles. -------------------- I point out this conjecture is "obviously false" in any dimension>=1 for a rotationally-symmetric ball. PROOF: start with generic rotationally symmetric heat distribution. (Hence eternally is rotationally symmetric.) At all future times, temperature is same everywhere on the boundary. Hence conjecture that the boundary includes the hottest point, contradicts conjecture it includes the coldest point. QED. However, I suppose the conjecturers will respond that my initial heat distribution was not generic enough, hence this is not really a disproof. In 1 dimension the 2nd eigenfunction of the interval [-pi, pi] is sin(x/2) which obeys the conjecture (and is odd- not even-symmetric). A proof the hotspots conjecture is false on the surface of a standard Moebius strip would follow if we knew the 2nd eigenfunction was cos(2*pi*y)*sin(2*pi*x) for the unit square 0<x<1, 0<y<1 with wraparound x mod 1 while reversing y. If you have the 2D surface of a 3D sphere, then the conjecture is false in the trivial sense there is no boundary :) If you make an initial heat distribution proportional to the z-coordinate, the min and max will forever be at the z-max and z-min "polar" locations. If you drill a tiny hole on the equator so this surface now does have a boundary, would that be a counterexample now with the same topology as a disc? If so, that would prove that topology and boundedness are not enough -- the actual zero-curvature geometry of the plane is also needed. -- Warren D. Smith http://RangeVoting.org

2 1

Re: [math-fun] The hot spots conjecture (statement of & a few remarks on)
by Dan Asimov 09 Jun '12

09 Jun '12

<< The hotspots conjecture can be expressed in simple English as: Suppose a flat piece of metal, represented by a two-dimensional bounded connected domain R, is given a generic initial heat distribution which then flows throughout the metal. Assuming the metal is insulated (i.e. no heat escapes from the piece of metal), then at all sufficiently large times, the hottest and coldest points on the metal both will lie on its boundary... . . . This conjecture has been proven for some domains and disproven for others. It is conjectured by Rodrigo Banuelos for any bounded simply-connected planar domain. . . . I point out this conjecture is "obviously false" in any dimension>=1 for a rotationally-symmetric ball. PROOF: start with generic rotationally symmetric heat distribution. (Hence eternally is rotationally symmetric.) At all future times, temperature is same everywhere on the boundary. Hence conjecture that the boundary includes the hottest point, contradicts conjecture it includes the coldest point. >> Why is the constant distribution excluded? --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Fwd: [New post] Polymath7 discussion thread - the Hot Spots conjecture
by Stuart Anderson 09 Jun '12

09 Jun '12

fyi ---------- Forwarded message ---------- From: The polymath blog <donotreply(a)wordpress.com> Date: Sat, Jun 9, 2012 at 3:50 PM Subject: [New post] Polymath7 discussion thread To: stuart.errol.anderson(a)gmail.com New post on The polymath blog Polymath7 discussion thread by Terence Tao The "Hot spots conjecture" proposal has taken off, with 42 comments as of this time of writing. As such, it is time to take the proposal to the next level, by starting a discussion thread (this one) to hold all the meta-mathematical discussion about the proposal (e.g. organisational issues, feedback, etc.), and also starting a wiki page (http://michaelnielsen.org/polymath1/index.php?title=The_hot_spots_conjecture) to hold the various facts, strategies, and bibliography around the polymath project (which now is "officially" the Polymath7 project). I've seeded the wiki with the links and references culled from the original discussion, but it was a bit of a rush job and any editing would be greatly appreciated. From past polymath experience, these projects can get difficult to follow from the research threads alone once the discussion takes off, so the wiki becomes a crucial component of the project as it can be used to collate all the progress made so far and make it easier for people to catch up. (If the wiki page gets more complicated, we can start shunting off some stuff into sub-pages, but I think it is at a reasonable size for now.) One thing I see is that not everybody who has participated knows how to make latex formatting such as appear in their comments. The instructions for that (as well as a "sandbox" to try out the code) are at this link. Once the research thread gets long enough, we usually start off a new thread (with some summaries of the preceding discussion) to make it easier to keep the discussion at a manageable level of complexity; traditionally we do this at about the 100-comment mark, but of course we can alter this depending on how people are able to keep up with the thread. Terence Tao | June 9, 2012 at 5:50 am | Categories: discussion | URL: http://wp.me/pAG2F-4k Initial webpage for proposal http://www.math.missouri.edu/~evanslc/Polymath/ A description of the problem http://www.math.missouri.edu/~evanslc/Polymath/Polymath.pdf The current discussion thread http://polymathprojects.org/2012/06/09/polymath7-discussion-thread/

1 0

[math-fun] Arbitrary bit permuting in O(log(wordsize)) steps; & demonstration this is optimal
by Warren Smith 08 Jun '12

08 Jun '12

I sketch a method (perhaps what FxtBook had in mind?) which should be able to perform an arbitrary fixed permutation of the W bits in a W-bit-long word in O(logW) steps. No future or weird machine instructions are needed -- the present non-weird ones will suffice. We break the problem down into SUBPROBLEMS of the following form: Divide the W-long word into chunks of lengths P,P,P,...,P where P is a power of 2. The even- and odd-numbered chunks are mentally red and blue. Then within 2 adjacent such chunks rrrrrrrrbbbbbbbb (here shown with P=8) the kth "r" is swapped (or not) with the kth "b" for all chunk-pairs and all k simultaneously, with independent swap-or-not decisions made for each bit-pair according to specification by certain W-bit long constants. It is known from the theory of telephone switching networks (e.g. the "Benes network" see http://en.wikipedia.org/wiki/Clos_network) that 2*lgW subproblem solves with P=W/2, W/4, ..., 4,2,1, 1,2,4, ..., W/4, W/2 successively will suffice to route any permutation, and it is fairly easy to figure out how using binary encodings. So: how can we solve that subproblem? Recall the well known (to those who know it) way to swap two words A, B without any temporary storage: A = XOR(A,B); B = XOR(A,B); A = XOR(A,B). Recall also the even-better-known fact that XOR(A,0)=A. So if we do A = XOR( A, B AND m); B = XOR(A AND m, B); A = XOR(A, B AND m) where m is a bitmask, then the mask=1 bits in A and B are swapped, and the rest left unswapped. Now in our problem "A" and "B" actually are different (red & blue) parts of the *same* machine word, but that is why God invented the arbitrary-hops bit-shift instruction and other bit masks specifying the coloring. QED[algorithm construction]. Now I also remark that this solution is OPTIMAL (up to a constant factor) in runtime because lg(W!) bits are needed to specify the permutation, i.e. at least lg(W) different W-bit long words are needed to specify it, and any machine which can only deal with a constant number of machines words at a time, necessarily will consume order log(W) timesteps just to see the specification. QED[optimality]. -- Warren D. Smith http://RangeVoting.org

1 1

[math-fun] Recursive binary tree representation for bignums in Lisp
by Henry Baker 08 Jun '12

08 Jun '12

I've been developing on a recursive binary/"really bignum" bignum package for Lisp where the "words" are in a binary tree instead of a linear list or vector, and the leaves are the (big) digits. However, I've included a quadtree-type optimization for long sequences of 0's or 1's, which has magical properties -- e.g., you get "carry-lookahead" for free! My representation is very similar to Jean Vuillemin's 2009 paper (referenced in the file), which doesn't have the quadtree-type optimization, although my representation was developed independently. Jean also uses sign-magnitude rather than 2's complement; 2's complement is much better for Lisp's logical operations on integers. As Vuillemin points out, Karatsuba squaring & multiplication is really ideal for this type of representation. This bignum package is obviously not complete today, but you can watch the progress here: http://home.pipeline.com/~hbaker1/rb.lsp At 12:35 PM 6/8/2012, Bill Gosper wrote: >In case anyone missed it, Knuth is strongly pushing MMIX's MOR and MXOR for commercial 64 bit processors. > >www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz

1 0

[math-fun] unrectifiable square wave?
by Bill Gosper 08 Jun '12

08 Jun '12

I randomly asked the kids for the limiting arclength of a period of a Fourier-approximated square-wave, and Neil surprised me by claiming it was infinite. Here's evidence in his favor. Just estimating the total variation of 2^n Gibbs wiggles (see http://www.tweedledum.com/rwg/gibbs.htm) In[45]:= Table[Block[{k = 0, p = N[π], p2}, p2 = p/2; Nest[(SinIntegral[k++*p] - p2)*(-1)^k + # &, 0, 2^n]], {n, 18}] The Nest is to avoid Mma's wonderful Sum and NSum, the latter of which reports substantial imaginary parts here. Out[45]= {1.85194, 2.10855, 2.3484, 2.57886, 2.80445, 3.02757, 3.24945, 3.4707, 3.69165, 3.91244, 4.13315, 4.35383, 4.57448, 4.79513, 5.01577, 5.23641, 5.45704, 5.67768} In[46]:= Differences[%] Out[46]= {0.25661, 0.239855, 0.230462, 0.225586, 0.223117, 0.221878, \ 0.221257, 0.220946, 0.220791, 0.220713, 0.220674, 0.220655, 0.220645, \ 0.22064, 0.220638, 0.220637, 0.220636} I.e., the nth Gibbs peak seems to die off like 1/n, too slowly to converge. So Sum[(SinIntegral[k*π] - π/2)*(-1)^k,{k,0,n}] ~ Log[b,n], where b ~ Log[2]/.220636 = 3.14159 . Hmm. I guess XKCD is OK with logs base π. --rwg

2 1