April 2014 - mathfun@mailman.xmission.com

[math-fun] no cloning
by Warren D Smith 07 Apr '14

07 Apr '14

"No cloning" theorem in quantum has nothing to do with fermions or boson. It is simply a fact about unitary transformations (e.g they are invertible, whilst "cloning" is not). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Knight-distance metric in chess
by Warren D Smith 07 Apr '14

07 Apr '14

Consider a bi-infinite chessboard (Z^2). What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves? [Incidentally, for a finite hXw chessboard, if min(h,w)>3 the bi-infinite and finite board exhibit the same distances in all cases except if the two squares are the corner of the board and diagonally adjacent to it, in which case the finite board has distance=4 while the bi-infinite board distance is 2.] After some fiddling, I came up with the following CONJECTURE: Define dx = |x1-x2|, dy = |y1-y2|, L1distance = dx + dy, KingDistance = max(dx, dy) F = ( max(2*L1distance, 3*KingDistance) + 4 ) / 6 Then KnightDistance = F rounded to the nearest eligible integer of the correct parity (correct parity: even if source and destination same-colored squares, otherwise odd) (eligible: must be non-negative, and if the two squares differ then must be positive) except for this list: (dx,dy) KnightDistance Formula (1,0) or (0,1) 3 1 (2,2) 4 2 (7,7) 4 6 in which my formula is off by 2. Are there any other exceptions? -- Warren D. Smith http://RangeVoting.org

10 20

[math-fun] Arndt bit reversal 32 request
by Warren D Smith 07 Apr '14

07 Apr '14

OK, another try. 32 = 27+5. Do the 27-reversal using 27=3*3*3 in "3 steps." Do the 5-reversal using a 32-entry lookup table in "1 step". Finally glue them together in reverse order. Sounds like "5 steps," which J.Arndt will reject as too many. However, really the 5+27 --> 27+5 swappage is done via a 5-hop rotation, which is got by a 5-hop left shift, a 27-hop right shift, and an OR. The word "and" here can be replaced by "and a table lookup, then". As a result, the whole algorithm is really i. 27-reverse in 3 steps. ii. 5+27 --> 27+5 swappage while inserting a 5->5 table lookup. This a 4 steps plus a table lookup, which is kind of "4 and a half steps." Plus..., you know you can do two 32-bit reversals at once using 64-bit reversal so on average faster :) ---------------------- Meanwhile, in case you care, I made a set of routines for dealing with 8-byte arrays as single 64-bit words, such as vector add, subtract, scale, additive shift by constant, subtract-with-saturation (negative results become 0), and sum-of-all-bytes, Many of these need to assume all byte values lie in [0..127]. Only the last two are nontrivial. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

[math-fun] Arndt bit reversal 32 request
by Warren D Smith 07 Apr '14

07 Apr '14

Observe that 32 = 12 + 8 + 12. 1.Reverse all runs of 4 bits. 2.Now reverse each of the 8, the 12, and the 12 by swapping their first with their last nybbles. 3.Finally swap the 12 & 12. How's that do? [Similarly 16=6+4+6 and 64=24+16+24.]

2 1

[math-fun] An identity by Wrench generalized
by Joerg Arndt 07 Apr '14

07 Apr '14

Knuth, TAOCP, vol.3, p.644, ex.27 gives the following identity, attributed to Wrench: sum(k>=1, A(k)*x^k / (1-x^k) ) = sum(k>=1, x^(k*k) * (A(k) + sum(j>=1, (A(k) + A(k+j)) * x^(k*j)) ) ) This can be verified by writing the terms in sum(k>=1, sum(j>=1, A(k) * x^(k*j) ) ) into a rectangular table and taking sums starting from the diagonal entries, simultaneously to the right and downwards. Just today I managed to find a generalization: sum(k>=1, A(k)*t^k / (1 - B(k)*x^k) ) = sum(k>=1, x^(k*(k-1)) * t^k * (A(k)*B(k)^(k-1) + sum(j>=1, ( A(k)*B(k)^(k+j-1)*x^j + A(k+j)*B(k+j)^(k-1)*t^j ) * x^(j*(k-1)) ) ) ) Setting t=x and B(k)=1 gives Wrench's identity. This is of a kind of formulas I am extremely fond of. Plus it is (at least computationally) even more general than R. P. Agarwal's identity for sum(n>=0, t^n/(1-x*q^n)) (see http://arxiv.org/abs/1202.6525 ) Should I sent this one to Knuth? Best, jj Pari code to verify: ----------------------- N=33; x='x+O('x^N); A(k)=eval(Str("a" k)); B(k)=eval(Str("b" k)); t2 = sum(k=1,N, A(k)*t^k / (1 - B(k)*x^k) ); { t6 = sum(k=1,N, x^(k*(k-1)) * t^k * (A(k)*B(k)^(k-1) + sum(j=1,N, ( A(k)*B(k)^(k+j-1)*x^j + A(k+j)*B(k+j)^(k-1)*t^j ) * x^(j*(k-1)) ) ) ); } t2-t6 \\ == zero (up to orders x^N and t^N) -----------------------

4 6

[math-fun] Article about ancient calculting tables
by David Wilson 06 Apr '14

06 Apr '14

http://english.pravda.ru/science/earth/27-01-2014/126683-ancient_chinese_cal culator-0/

3 3

Re: [math-fun] Article about ancient calculting tables
by Henry Baker 06 Apr '14

06 Apr '14

Yup! http://en.wikipedia.org/wiki/List_of_book-burning_incidents The U.S. also went to great lengths to try to stamp out native American culture, including language. MIT has recently helped recreate the native American language on Cape Cod, in one attempt to reverse a small portion of this history. At 07:16 AM 4/6/2014, Fred Lunnon wrote: >Maybe Mao's "great leap forward" (sic) observed a well-established custom after all >--- who knew?

1 0

[math-fun] knight distance
by Warren D Smith 05 Apr '14

05 Apr '14

OK, I did a comprehensive computer check of both my algorithm and Lunnon's equivalent algorithm both of which conjecturally compute knight distance for bi-infinite chessboard. Result: when max(|x|, |y|)<20000, Lunnon's & my algorithms indeed are equivalent, and indeed do compute knight distance. At least the way I coded them in C [C is somewhat annoying for this since a/b returns result rounded toward zero, NOT floor(a/b)] the timings were WDS: 29.3 seconds Lunnon: 26.2 seconds (Lunnon's lemma 2 is unproven and the reason is global, its entire proof was just wrong. Sorry I can't be more specific, but if you want me to point out a specific error you have to make a specific error.) However, there seems no doubt now about correctness of the conjecture. Here is C code int fLunnon(int x, int y){ int X,Y,p,q; if(x<0){ x = -x; } if(y<0){ y = -y; } if(x<y){ X=y; Y=x; }else{ X=x; Y=y; } if(X<=2){ if(X==1 && Y==0){ return(3); } if(X==2 && Y==2){ return(4); } } p = X-Y; q = p-Y; if(q<0){ return( p + 2*( (q%3!=0) - q/3 ) ); } return( p - 2*(q/4) ); } int g(int x, int y){ int b,c; b = f(x-2,y-1); c = f(x-1,y-2); if(c<b){ b=c; } c = f(x+2,y-1); if(c<b){ b=c; } c = f(x+1,y-2); if(c<b){ b=c; } c = f(x+2,y+1); if(c<b){ b=c; } c = f(x+1,y+2); if(c<b){ b=c; } c = f(x-2,y+1); if(c<b){ b=c; } c = f(x-1,y+2); if(c<b){ b=c; } return( f(x,y) - b ); } TO PROVE: g(x,y)=1 unless x=y=0, then g(0,0)=-1.

2 1

[math-fun] schrodinger NP-complete? Actually...
by Warren D Smith 05 Apr '14

05 Apr '14

In this paper by me Church's thesis meets quantum mechanics paper #49 here http://rangevoting.org/WarrenSmithPages/homepage/works.html it was proven that solving the quantum N-body problem is "efficiently simulable" in a certain sense. This sense is, with probability 99.99999999%, easier than NP-complete, i.e. my paper "proves" this is NOT and cannot be, NP-hard. The reason proves is in quotes is that this is only true if certain well known conjectures about NP are true (e.g. P not equal NP).

1 0

[math-fun] P vs. NP Problem Linked To the Quantum Nature of the Universe
by Ray Tayek 05 Apr '14

05 Apr '14

http://science-beta.slashdot.org/story/14/04/04/1610237/p-vs-np-problem-lin… <http://beta.slashdot.org/%7ESoulskill>Soulskill (1459) posted 11 hours ago | from the schrodingers-cat-is-both-alive-and-equal-to-NP dept. <http://science-beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: "One of the greatest mysteries in science is why we don't see quantum effects on the macroscopic scale; why Schrodinger's famous cat cannot be both alive and dead at the same time. Now <https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a>one theorist says the answer is because P is NOT equal to NP. Here's the thinking: The equation that describes the state of any quantum object is called <http://en.wikipedia.org/wiki/Schrodingers_equation>Schrodinger's equation. Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself. But the new idea is that this requires an additional assumption that an efficient algorithm exists to solve the equation for complex macroscopic systems. But is this true? The <http://arxiv.org/abs/1403.7686>new approach involves showing that the problem of solving Schrodinger's equation is <http://en.wikipedia.org/wiki/Np-hard>NP-hard. So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently. And because all NP-hard problems are mathematically equivalent, this algorithm must also be capable of solving all other NP-hard problems too, such as the traveling salesman problem. In other words, NP-hard problems are equivalent to the class of much easier problems called P. Or P=NP. But here's the thing: computational complexity theorists have good reason to <http://en.wikipedia.org/wiki/P%3Dnp>think that P is not equal to NP (although they haven't yet proven it). If they're right, then macroscopic superpositions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!" --- co-chair http://ocjug.org/

3 3