July 2014 - mathfun@mailman.xmission.com

[math-fun] "period" 6
by Bill Gosper 14 Jul '14

14 Jul '14

In[360]:= Table[GoldenRatio^n*Sin[π*GoldenRatio^n] // N[N[#, 99]] &, {n, 69, 105}] Out[360]= {3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, -3.14159, -3.14159, -3.14159, 3.14159, 3.14159} --rwg

2 2

[math-fun] Post-quantum proof-of-work system?
by Adam P. Goucher 13 Jul '14

13 Jul '14

The usual proof-of-work system involved in things such as Bitcoin mining is the following: "Find a string S such that hash(S) begins with n leading zeroes" A classical probabilistic computer can do this with O(2^n) operations (which are very parallelisable), whereas a quantum computer can do this with O(2^(n/2)) operations using Grover's algorithm (which is not parallelisable). Nevertheless, this would give quantum computers significant advantage over their classical counterparts in Bitcoin mining. Instead, I propose the following alternative proof-of-work system: "Find two distinct strings, S and T, such that hash(S) and hash(T) agree in the first n bits" Now, a classical probabilistic computer with memory O(2^(n/2)) can do this in time O(n 2^(n/2)) by doing the following: 1. Create O(2^(n/2)) distinct strings; 2. Hash them; 3. Quicksort the hashes, and compare adjacent entries to see whether any agree. The probability of success as a function of n is bounded below due to the birthday paradox. A quantum computer using Grover's algorithm would take O(2^(n/2)) time with the following method: 1. Create a string S; 2. Search for a distinct string T whose hash agrees with S in the first n bits. And O(2^(n/2)) is only slightly faster than O(n 2^(n/2)), and the difference is probably engulfed into the constant factor involved in implementing a fault-tolerant quantum computer. Hence quantum computers have no real advantage over classical computers, except for requiring less memory. Sincerely, Adam P. Goucher

4 3

Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
by Bill Gosper 12 Jul '14

12 Jul '14

Dan Asimov wrote: < RWG wrote: < For a ceremonial match, a soccer ball is colored with a map of the Globe instead of a traditional pattern. At the start of the match, the ball rests on its south pole, with its lat 0, long 0 point aimed due east. At the end of the match, the ball lies forgotten on the pitch, in a truly random orientation. For any orientation, there will always be an axis through the center about which a single rotation will restore the original north up, 0,0 east orientation. What is the (surprising) expected magnitude of this required rotation? >RWG SPOILER SPACE ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... SOLUTION: --------- We want to find the average distance in the rotation group SO(3) between an arbitrary rotation and the identity, where distance is measured by the angle t of the rotation, 0 <= t <= pi. (*) Every rotation f in SO(3) is represented by either of exactly two unit quaternions, which are antipodal. This works by first identifying S^2 with the unit sphere in S^3 that is the equator with respect to the poles +-1. Then for any x in S^2, the rotation f_q(x) is defined by f_q(x) = q' x q where q' denotes the reciprocal of q (for a unit quaternion, just its conjugate). If t is the least angle between q and the real axis (so that 0 <= theta <= pi/2), then the rotation f_q is by an angle of 2t. We can now find the average rotation angle from the identity among all rotations in SO(3). By (*), SO(3) corresponds almost exactly to the hemisphere Hem^3 of S^3 nearest to the identity . . . except that those points farthest from the identity, forming a copy of a unit 2-sphere, need to be identified by the antipodal map to get just one quaternion for each rotation. But since this 2-sphere is measure 0 inside Hem^3, we can ignore this nicety to find the average rotation angle. All the quaternions q of Hem^3 at angle t > 0 from the identity form a locus that is a 2-sphere of radius = sin(t). For all these q, the rotation angle of the rotation f_q is 2t., and their 2-volume is 4 pi sin^2(t). The total 3-volume of the (unit) 3-sphere S^3 is 2 pi^2, so that of Hem^3 is just pi^2. So we get for the probability density of the angle t d(t) = 4 pi sin^2(t) / pi^2 and so the expected rotation angle is E(2t) = Integral_{0,pi/2} (2t) 4 pi sin^2(t) dt / pi^2 = (8/pi) Integral_{0,pi/2} t sin^2(t) dt = pi/2 + 2/pi . Which is pretty mystical. Makes you wonder if there isn't some good reason it turns out like that. --<Dan In perfect agreement with http://people.csail.mit.edu/bkph/other/Stanford_AI_WP_79_Salamin.pdf . So *two* of you would've gotten it, if you're both Numberplayers!-) What a neat variation on Buffon's needle--no stripes required. No ball required either if we Monte Carlo. Of course, it might be hard to write the latter w/o using π. If so, maybe it would converge if we start with 3 and modify the Monte Carlo as our knowledge of π improves. --rwg

1 1

Re: [math-fun] Chebyshev points for real interval [-1, 1], pretty picture
by Henry Baker 11 Jul '14

11 Jul '14

Everyone on math-fun should be aware of the really cool "Chebfun" system, which is a computer algebra system by Nick Trefethen of Oxford University based on Chebyshev polynomials. There's also a good video lecture (on Youtube?) which gives a nice overview. https://en.wikipedia.org/wiki/Chebfun http://www.chebfun.org/ http://www.chebfun.org/ATAP/ http://people.maths.ox.ac.uk/trefethen/chebfun.pdf https://people.maths.ox.ac.uk/trefethen/cheb2paper.pdf http://www.cs.berkeley.edu/~fateman/papers/cheby.pdf

1 0

[math-fun] Quaternions & vectors, yet again
by Henry Baker 11 Jul '14

11 Jul '14

Given vectors A,A',B,B', such that qAq*=A' and qBq*=B', |A'|=|A|, |B'|=|B|, find q. (q* is conjugate of q.) Taking norms, we find that qq*=1. Let dA=A'-A and dB=B'-B. Then the axis of rotation is dAxdB. This means that the vector part of q is perpendicular to both dA and dB. We will split A,B,A',B' into parts that are parallel to the rotation axis and parts that are perpendicular to the axis: A = Apar + Aper B = Bpar + Bper A' = Apar + (Aper + dA) B' = Bpar + (Bper + dB) qAq* = q(Apar + Aper)q* = q(Apar)q* + q(Aper)q* = qq* Apar + q^2 Aper (Lemma from previous post) = Apar + q^2 Aper = Apar + (Aper+dA) So, q^2 Aper = Aper+dA, or q^2 = (Aper+dA)/Aper = 1+dA/Aper. ("/" here means quaternion division.) Similarly, q^2 = 1+dB/Bper. Checking, we find that the vector part of q is parallel to the vector part of q^2. Furthermore, the vector part of dA/Aper is a multiple of dAxAper which is the same axis as dB/Bper which is a multiple of dBxBper. These are all parallel to dAxdB. We note that even when |A|=|A'|/=|B|=|B'|, |dA/Aper|=|dB/Bper|, so dA/Aper=dB/Bper in both magnitude and direction. So we now need to compute Aper, Bper. If S=dAxdB, then Aper = SxAxS/(S.S) Bper = SxBxS/(S.S) (Note that "x" associates in this particular instance.) Thus, S=dAxdB and q = +- sqrt(1+(S.S)dA/SxAxS) = +- sqrt(1+(S.S)dB/SxBxS) is the quaternion we seek. (It would still be interesting to find an expression for this quaternion that didn't involve dot or cross products; i.e., only the rational operations +,-,*,/ and sqrt.)

1 0

[math-fun] Constant velocity implies round wheels?
by James Propp 11 Jul '14

11 Jul '14

This question (in a square-wheeled-tricycle vein) is probably easy, but I haven't had any coffee yet so it's not easy for me! If you want a tricycle with wheels of some shape, riding on a terrain of some shape, so that turning the pedals with constant angular velocity (relative to the pedal-axle) imparts constant linear velocity to the rider, must the wheels be round and the terrain be flat? On a square-wheeled tricycle, the forward speed of the tricycle varies; this is one reason why the ride does not feel as smooth as one might like. Jim Propp

3 6

[math-fun] WIlsonian sums of 1/(n+k) and 1/(n+k)^2, and linear relations among them
by Warren D Smith 10 Jul '14

10 Jul '14

Wilsonian sums can be computed by the following recursive routine, which I have found (at least for table below) returns a lot more accuracy than the naive sequential-sum approach (due to smaller floating point roundoff errors). //Wsum(0,k) finds the "Wilsonian tree sum" of f(n) for n=0,1,..., 2^k-1. real wsum(uint offset, int depth){ if(depth<=1){ if(depth==1){ return( f(offset)-f(offset+1) ); } return( f(offset) ); } depth = depth-1; return( wsum(offset, depth) - wsum(offset+(1<<depth), depth) ); } Looking at what Gosper & Julian were doing... I made this table of (what they were calling) a[j]. As an indication of convergence speed, depth=11 already suffices to attain full machine accuracy for a[1] using above routine. Julian proved the linear relations a[k]=a[k+1]+2a[2k]+2a[2k+1]. To verify a1 = 3*a2+2*a3: 0.3987610881084188 = 0.1049709156498952 * 3 + 0.0419241705793666 * 2 confirmed to all decimal places. However there are more linear relations beyond the Gosper-Hunt family: a[2] = a[3] + 2*a[4] + 2*a[5] a[3] = a[4] + 2*a[6] + 2*a[7] a[4] = a[5] + 2*a[8] + 2*a[9] a[5] = a[6] + 2*a[10] + 2*a[11] ... such as a[2] = a[3] + 2*a[4] + 2*a[5] a[3] = a[4] + 2*a[6] + 2*a[7] a[4] = a[5] + 2*a[8] + 2*a[9] a[5] = a[6] + 2*a[10] + 2*a[11] ... a[1] = 2*a[2] + 3*a[3] + 2*a[4] + 2*a[5] a[2] = 3*a[4] + 2*a[5] + 2*a[6] + 2*a[7] a[1] = 5*a[3] + 6*a[4] + 6*a[5] 5*a[2] = a[1] + 8*a[5] + 8*a[8] + 8*a[9] 5*a[2] = a[1] + 4*a[4] + 4*a[5] I have a huge list of these... table of "Wilsonian sums" of 1/(1+j) for each j=1..32: j SUM( h(n) / (n+j) for n=0..2^k-1 in limit of large k --- ------------------------------------------------------- 1 0.3987610881084188 2 0.1049709156498952 3 0.0419241705793666 4 0.0203750966130826 5 0.0111482759221817 6 0.0066128424114721 7 0.0041616945716699 8 0.0027411489242099 9 0.0018722614212406 10 0.0013173970994978 11 0.0009503196558569 12 0.0007001840370244 13 0.0005253898828767 14 0.0004005619577615 15 0.0003097108659685 16 0.0002424742647055 17 0.0001919694867792 18 0.0001535248009690 19 0.0001239073599023 20 0.0001008409648011 21 0.0000826977570194 22 0.0000682969401414 23 0.0000567708692748 24 0.0000474744168942 25 0.0000399226601797 26 0.0000337474197261 27 0.0000286665428315 28 0.0000244619271800 29 0.0000209636187166 30 0.0000180381829930 31 0.0000155801176385 32 0.0000135054521681 And here is the corresponding table for squared denominator: table of "Wilsonian sums" of 1/(1+j)^2 for each j=1..32: j SUM( h(n) / (n+j)^2 for n=0..2^k-1 in limit of large k --- --------------------------------------------------------- 1 0.6931534522180850 2 0.1117650400949581 3 0.0335820629358237 4 0.0133237967727124 5 0.0062219475170712 6 0.0032397035956294 7 0.0018248629451484 8 0.0010912827018934 9 0.0006841796120168 10 0.0004457425663512 11 0.0002998184140093 12 0.0002071838292345 13 0.0001465263333858 14 0.0001057349601303 15 0.0000776601006835 16 0.0000579399143162 17 0.0000438358581530 18 0.0000335845447693 19 0.0000260247166471 20 0.0000203761188256 21 0.0000161049192598 22 0.0000128398456509 23 0.0000103188005428 24 0.0000083542143978 25 0.0000068101595644 26 0.0000055869866897 27 0.0000046108566242 28 0.0000038265094055 29 0.0000031922054562 30 0.0000026761444430 31 0.0000022539021488 32 0.0000019065770308 and it found many linear relations for these too (call these b[j]), here are the first few of my list of 382 such: 1*b[1] + -7*b[2] + -2*b[3] + 8*b[4] + 8*b[5] = 0.0000000000000001 1*b[1] + -6*b[2] + -3*b[3] + 4*b[4] + 4*b[5] = 0.0000000000000001 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -4*b[2] + -5*b[3] + -4*b[4] + -4*b[5] = 0.0000000000000001 1*b[1] + -3*b[2] + -6*b[3] + -8*b[4] + -8*b[5] = 0.0000000000000001 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 1*b[1] + -5*b[2] + -4*b[3] = 0.0000000000000002 -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 3

[math-fun] Chebyshev points for real interval [-1, 1], pretty picture
by Warren D Smith 10 Jul '14

10 Jul '14

This picture https://dl.dropboxusercontent.com/u/3507527/Chebyshev175nrpi.png shows the Chebyshev 175-point set -- whose (unweighted) first 175 moments agree with those of the (uniform distribution on the) real interval [-1,1]. Caveats: Unfortunately the polynomial root solver has numerical difficulties so it is dubious these are very accurate. (If I try for 201 points it totally dies.) Only points with non-positive real part and non-negative imaginary part are shown, i.e. this is one quarter of the full picture. So it appears Chebyshev ultimately is approximating the real interval with an ellipse (or something close to it) plus a few stragglers, perhaps on another curve. Pretty interesting, whatever the hell it is. A natural guess is that the ellipse has foci at +-1. It would be good to produce a more-accurate plot of, say, the 1001-point set. Here is how to tell "maxima" to compute the 51 point set: f(N) := taylor( exp( (N/2)*(log(1-z^2) + (2/z)*atanh(z) - 2) ), z, 0, N); g(N) := subst(1/x, z, trunc(f(N))) * x^N; expand(g(51)); allroots(%); In words: find the Maclaurin series of exp( (N/2)*(log(1-z^2) + (2/z)*atanh(z) - 2) ) in powers of z from z^0 up to and including z^N, this is a polynomial in z. Now replace z by 1/x, then multiply the whole thing by x^N, to get the "reversed" degree-N polynomial, which is monic. Now find its roots. The result is the Chebyshev N-point set. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2

[math-fun] Wilsonian sums of 1/sqrt(n+k) and sqrt(n+k), and linear relations among them
by Warren D Smith 10 Jul '14

10 Jul '14

For both of the following, no integer linear relations appear to exist. table of "Wilsonian sums" of 1/sqrt(1+j) for each j=1..32: j SUM( h(n) / sqrt(n+j) for n=0..2^k-1 in limit of large k --- ----------------------------------------------------------- 1 0.1983140804979377 2 0.0648679674894559 3 0.0294926839418280 4 0.0157413778643092 5 0.0092727250186152 6 0.0058468071083846 7 0.0038768346692010 8 0.0026728045984540 9 0.0019012236938776 10 0.0013876178483701 11 0.0010348719377425 12 0.0007861585985739 13 0.0006068222719239 14 0.0004749802427539 15 0.0003763975850233 16 0.0003015724778226 17 0.0002440176120376 18 0.0001992145334106 19 0.0001639596428052 20 0.0001359450434934 21 0.0001134839819466 22 0.0000953274430131 23 0.0000805394456847 24 0.0000684108748084 25 0.0000583990578796 26 0.0000500848191169 27 0.0000431415737542 28 0.0000373128299688 29 0.0000323956358195 30 0.0000282282789730 31 0.0000246810617323 32 0.0000216493224597 No linear relations found. table of "Wilsonian sums" of 1/sqrt(1+j) for each j=0..32: j SUM( h(n) / sqrt(n+j) for n=0..2^k-1 in limit of large k --- ----------------------------------------------------------- 0 -0.6340742633208627 1 -0.1087899444969256 2 -0.0515209115743647 3 -0.0294697315032235 4 -0.0186280444431191 5 -0.0125570333423308 6 -0.0088605088234095 7 -0.0064719521202861 8 -0.0048578149370044 9 -0.0037278911614336 10 -0.0029139993988712 11 -0.0023136758922906 12 -0.0018619065384380 13 -0.0015160228631279 14 -0.0012472097270808 15 -0.0010355247113232 16 -0.0008668689001796 17 -0.0007310847509929 18 -0.0006207330180334 19 -0.0005302837800949 20 -0.0004555701919706 21 -0.0003934154098761 22 -0.0003413704416433 23 -0.0002975279275219 24 -0.0002603886226424 25 -0.0002287648004256 26 -0.0002017072431677 27 -0.0001784519084129 28 -0.0001583801579947 29 -0.0001409873564580 30 -0.0001258597327007 31 -0.0001126559549967 32 -0.0001010928558065 No linear relations found.

1 0

[math-fun] gears
by Warren D Smith 10 Jul '14

10 Jul '14

Yes, gears (if designed right) do attain constant angular velocity and contacting 100% of time. However, unlike wheels they do not "roll"; they always slide. The theory shows this is inevitable. See this paper by me to learn about gear theory and the least-friction gear curve (found by me) which could use some numerical exploration...: http://rangevoting.org/WarrenSmithPages/homepage/works.html paper #23. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0