April 2014 - mathfun@mailman.xmission.com

Re: [math-fun] What if Turing/Shannon/Bekenstein were wrong?
by Henry Baker 09 Apr '14

09 Apr '14

I don't see how it is possible for the number of photons to be conserved as the universe expands. Experiment #1. Flat 3D space; no expansion. A flash of green light at the origin expands in a spherical shell (as is usual in odd-dimensional spaces). The intensity of this green light goes down as 1/r^2 as the spherical shell of radius r expands, but the light remains exactly the same green color. The number of photons is conserved. Experiment #2. Flat, but expanding 3D space. A flash of green light at the origin expands in a spherical shell, and the light becomes redder. Since red photons have less energy than green photons, there must be more of them to conserve the same energy from the initial flash. QED At 04:45 PM 4/8/2014, Eugene Salamin wrote: >>No, as the universe expands, the number of photons is conserved.

2 1

Re: [math-fun] What if Turing/Shannon/Bekenstein were wrong?
by Adam P. Goucher 09 Apr '14

09 Apr '14

"...and the light becomes redder." Are you sure about that? I don't think the inflation of the universe would alter the wavelength of a photon; that seems utterly impossible. Red-shift is a relativistic effect, namely that if two observers are travelling at different speeds, they will disagree what wavelength a particular photon has. This is totally unrelated to the inflation of the universe. Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Henry Baker > Sent: 04/09/14 04:49 PM > To: Eugene Salamin, math-fun > Subject: Re: [math-fun] What if Turing/Shannon/Bekenstein were wrong? > > I don't see how it is possible for the number of photons to be conserved as the universe expands. > > Experiment #1. Flat 3D space; no expansion. > > A flash of green light at the origin expands in a spherical shell (as is usual in > odd-dimensional spaces). > > The intensity of this green light goes down as 1/r^2 as the spherical shell of radius r expands, > but the light remains exactly the same green color. > > The number of photons is conserved. > > Experiment #2. Flat, but expanding 3D space. > > A flash of green light at the origin expands in a spherical shell, and the light becomes redder. > > Since red photons have less energy than green photons, there must be more of them to conserve > the same energy from the initial flash. > > QED > > At 04:45 PM 4/8/2014, Eugene Salamin wrote: > >>No, as the universe expands, the number of photons is conserved. > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

[math-fun] Intel x86: Whose Fault Is It ?
by Henry Baker 09 Apr '14

09 Apr '14

FYI -- How to "compute" on the x86 architecture without actually executing any instructions! You set up memory in such a way that everything you do _faults_ from one place to another, but this faulting is Turing complete! (No instructions were executed in the development of this computation.) If HAKMEM (The Next Generation) ever happens, this item will definitely qualify. The Page-Fault Weird Machine: Lessons in Instruction-less Computation Authors: Julian Bangert, Sergey Bratus, Rebecca Shapiro, and Sean W. Smith, Dartmouth College Trust Analysis, i.e. determining that a system will not execute some class of computations, typically assumes that all computation is captured by an instruction trace. We show that powerful computation on x86 processors is possible without executing any CPU instructions. We demonstrate a Turing-complete execution environment driven solely by the IA32 architectures interrupt handling and memory translation tables, in which the processor is trapped in a series of page faults and double faults, without ever successfully dispatching any instructions. The "hard-wired" logic of handling these faults is used to perform arithmetic and logic primitives, as well as memory reads and writes. This mechanism can also perform branches and loops if the memory is set up and mapped just right. We discuss the lessons of this execution model for future trustworthy architectures. Presentation Video Download Video Presentation Audio The paper: http://www.cs.dartmouth.edu/~sws/pubs/bbss13.pdf The presentation video: https://www.usenix.org/conference/woot13/workshop-program/presentation/bang…

1 0

[math-fun] knight distance proof (answers to questions)
by Warren D Smith 09 Apr '14

09 Apr '14

Lunnon questioning WDS: As I understand this, you want to enumerate all possible combinations of rounding after division by r = 3 or 4 following branch on sign(q); so where does your bound max(|x|, |y|) < 2999999 come from? --it was to provide enough safety. My idea was to use brute force to avoid thinking. Since thinking clearly does not work well :) > You must ensure f(x, y) > 4 to avoid tangling with special values; > given that, the rounding behaviour of your g simply repeats as |x|, |y| > repeat modulo 12 . So it seems to me that you need only check > f(x, y) = 1 + min( f(x-2, y-1), ..., f(x+2, y+1) ) > in (one octant of) region max(|x|, |y|) <= 16 ! --maybe but I'm skeptical. I needed to work mod 24. Maybe mod 12 will do, but I played it safe. Anyhow, that indicates brute force confirmation region must extend at least 24*(something decently large) to make sure of self. Similarly the boundary regions I used on my cases were 50-wide to avoid worries re 24, etc etc. Again suggesting you better brute force it substantially further than 50. To be ultra sure I multiplied 50*24*24*3*SafetyFactor to get 2999999 as bound delineating brute force region which definitely should be safe. I'm sure one could avoid a lot of this brute force, but the more you avoid, the more likely you'll go wrong.

1 0

[math-fun] What if Turing/Shannon/Bekenstein were wrong?
by Henry Baker 08 Apr '14

08 Apr '14

I was listening to some of Leonard Susskind's lectures on black holes & information & the fight with Hawking yesterday, and they seemed almost quaint. The reason is that information theory & computer science are 100% classical. Computer science and information theory are founded on the principle that information can be copied, while the "no-clone" theorem of quantum mechanics states that quantum states cannot be cloned. These two distinct views of the world cannot be reconciled, except at scales large enough whereby a quantum system can simulate (with great effort & inefficiency) a classical computer circuit. Szilard was making significant progress on Maxwell's Demon and information in the 1920's, when quantum mechanics knocked the foundation out from under Maxwell's entire enterprise. Shannon's theorems re the information-carrying bandwidth are entirely classical, and completely ignore the quantum nature of radio/light waves. Thus, de Broglie tells us that long wavelengths contain many more quanta than short wavelengths. (In fact, the number of quanta is essentially the number of Planck lengths contained in the wavelength.) But Shannon tells us that shorter wavelengths can contain _more_ information than longer wavelengths! I call this the "ultraviolet catastrophe" of information theory. The Bekenstein argument talks about dropping information into a black hole & calculating the change in size of the black hole that results. But you can't drop "information", per se, into a black hole; you can only drop actual quantum mechanical particles into a black hole. These quantum mechanical particles may be entangled with particles outside the black hole. Thus, the Bekenstein argument re how much classical Shannon "information" can be stored in a black hole is interesting, but ultimately irrelevant. Shannon information theory ultimately rests on probability theory, which is also quintessentially classical. A proper modern _quantum_ information theory would rest instead on a _quantum_ probability theory in which the standard 2-slit results fall out naturally. The two articles below re evading the "diffraction limit" with quantum entangled photons demonstrates once again how far from reality our standard classical viewpoint really is. The recent discussion here re P=NP and quantum systems misses an important point: whether P=NP (a classical notion in a classical framework) may be completely irrelevant in the real quantum world. Modern computer science is fundamentally built on Turing machines that _copy information_ from one place to another. This is the basis of simulation and universal computers. But the entire enterprise fails when we can't even copy one quantum bit. We even require a new type of logic to deal with this problem: so-called "linear logic", which deals with things that can't be copied -- e.g., resources like time, space, energy, etc. It will probably take the rest of the 21st Century to re-invent probability, information theory and computer science, but we need to start soon in order to make even this long deadline. --- http://www.technologyreview.com/view/524521/worlds-first-entanglement-enhan… February 10, 2014 World's First Entanglement-Enhanced Microscope Physicists have long known that entangled photons can make more precise measurements than independent ones. Now Japanese physicists have built a microscope that proves it. One of the exciting possibilities of quantum mechanics is the ability to measure the world far more precisely than with classical tools. Today, Takafumi Ono and pals at Hokkaido University in Japan say theyÂve exploited this to create the worldÂs first entanglement-enhanced microscope. Their new toy produces images with entangled photons that are significantly sharper than those possible with ordinary light alone. Entanglement is the strange quantum property in which two particles share the same existence, even though they may be far apart. Ono and co say this is particularly useful for a type of imaging known as differential interference contrast microscopy. This works by focusing two beams of photons into spots next to each other on a flat sample and measuring the interference pattern they create after they have been reflected. When both spots hit a flat part of the sample, they travel the same path length and create a corresponding interference pattern. But when the spots hit areas of different heights, the interference pattern changes. It is then possible to work out the shape of the surface by analysing the change in the interference pattern as the spots move across it. The difference in phase of photons can be measured with huge accuracy, but even this has a limit, known as the standard quantum limit. However, physicists have known for some time that itÂs possible to improve on this by using entangled photons rather than independent ones. ThatÂs because a measurement on one entangled photon gives you information about the other, so together they provide more information than independent photons. Ono and co demonstrate this using entangled photons to image a flat glass plate with a Q-shaped pattern carved in relief on the surface. This pattern is just 17 nanometres higher than the rest of the plate and so tricky to resolve with ordinary optical techniques. Entangled photons significantly improve on this. Ono and co say the signal to noise ratio using their technique is 1.35 times better than the standard quantum limit. And the resulting image is noticeably improved, simply by visual inspection (the image with entangled photons is on the left in the above figure). ÂAn image of a Q shape carved in relief on the glass surface is obtained with better visibility than with a classical light source,Â they say. That should be useful in a number of different applications; when samples might be damaged by intense light, for example. Enhanced microscopy is just one of many applications for quantum metrology. It should also help improve the resolution of the interferometers used in gravitational wave astronomy, for example. So itÂs good to see a success like this in another area. Ref: arxiv.org/abs/1401.8075: An Entanglement-Enhanced Microscope https://medium.com/p/5f473cf5a4bc How To Build A Quantum Telescope Quantum optics has revolutionised microscopy. Now astronomers are planning to jump on the quantum bandwagon The Physics arXiv Blog in The Physics arXiv Blog The diffraction limit is astronomyÂs greatest enemy. The resolution of all telescopes is limited by factors such as imperfections in the optics and turbulence in the atmosphere. But these can be overcome using better equipment, adaptive optics and by getting above the atmosphere. But there is one limit that astronomers cannot overcome because it is set by the laws of physicsÂ-the diffraction limit. Every telescope on the planet, and all those orbiting it, are limited in this way. And until recently there was no known way to beat it. Now physicists have begun to develop various quantum techniques that can overcome the diffraction limit, at least in the lab. These techniques have begun to revolutionise microscopy, where the light source can be carefully controlled. But they have yet to be considered for astronomy because astronomers have little, if any, control over the sources of the light they are interested in. Today, however, Aglae Kellerer at the University of Durham explains how to build a quantum telescope. She says quantum techniques could dramatically improve the resolution of telescopes by beating the diffraction limit for the first time. When light from a point source enters a lens, it bends. This bending causes the light to spread out so that it interacts with itself generating an interference pattern. The result is that a lens always resolves a point source as a bright disc surrounded by concentric circles of light, a pattern known as an Airy disc. The size of this disc, which is determined by the wavelength of light and the size of the lens, determines the ultimate resolution of the instrument. In practice, most telescopes are limited by other factors, in particular, turbulence in the several kilometres of atmosphere above them. But techniques such as adaptive optics, which iron out the effects of turbulence, are allowing telescopes to get much closer to the diffraction limit. So how to go further? KellererÂs idea is to exploit the strange effects of quantum mechanics to improve things. Entanglement, for example. Entangled photons are so deeply linked that they share the same existence. Measure one and you automatically influence the other. That gives you information about the other photon, regardless of its distance from you. Last month, physicists used this idea to build the worldÂs first entanglement-enhanced microscope that dramatically increases its resolution over purely classical instruments. They created entangled photons and used one to illuminate the object. The second photon can then give them information about the first that they use to increase the resolution of the resulting image. ThereÂs an obvious problem in employing these kinds of techniques in astronomyÂ-the photons of interest arenÂt under your control, having travelled many lightyears from their astrophysical source. But Kellerer says there is a way round this. Her idea is to use the astrophysical photons to stimulate the production of an entangled pair, inside a telescope. The first of this pair then hits the detector, generating an image. But the other can be used to increase the information known about the first, thereby increasing the resolution and beating the diffraction limit. ThatÂs an interesting idea that has the potential to significantly increase the resolution of conventional telescopes. In fact, Kellerer has simulated the effect of this process on computer to enhance the resolution of a conventional astronomical image by a factor of six. But building an instrument that works in this way will be hard and the devil is in the detail. The first problem is in producing entangled photons in the first place. KellererÂs idea is to use a crystal of excited atoms that emit entangled photons when stimulated by passing astrophysical ones. The problem is the efficiency of such a process. With so few astrophysical photons to play with, any that are lost due to inefficiencies are a serious problem. Then there is the problem of spontaneous emission. Excited atoms have a nasty habit of emitting photons, even when they are not stimulated by passing photons. ThatÂs noise, which could end up overwhelming the signal from the photons astronomers are interested in. Both of these problems can be minimised but they cannot be removed completely. The question is whether the advantages of this technique can be made to outweigh the disadvantages in a real device. ThereÂs only one way to find out, of course. Today, the technology required to test this idea is in its infancy. But thereÂs good reason to think that significant advances will be made in the near future. And that means that future telescopes could be very different from the ones we have today. ItÂs a sobering thought that if the pioneers of telescopic imaging were around today, they would find that the worldÂs best telescopes work in more or less exactly the same way as their own from 400 years ago. But KellererÂs approach would be entirely alien to them and could finally take astronomy into a new era of quantum imaging. Ref: arxiv.org/abs/1403.6681 : Quantum Telescopes

5 15

[math-fun] Jstor & Activists
by Eric Angelini 08 Apr '14

08 Apr '14

Hello Math-fun, If I'm not wrong, some complaints about Jstor's paywall policy occurred here. This could be of interest: https://www.yahoo.com/tech/one-artist-is-printing-250-000-pages-of-pirated-… Best, É.

1 0

Re: [math-fun] What if Turing/Shannon/Bekenstein were wrong?
by Henry Baker 08 Apr '14

08 Apr '14

A single cycle of a wave; i.e., from 0 to 2pi. This is my whole point: one way of looking at the quantum nature of electromagnetic waves is that it hints at the graininess of space itself. The wave is getting "sampled" by this grainy space into individual quanta. At 08:12 AM 4/8/2014, Eugene Salamin wrote: >> From: Henry Baker <hbaker1(a)pipeline.com> >>A single photon of an electromagnetic wave of wavelength lambda has energy E = h*c/lambda. >> >>The energy of a complete wave is computed by multiplying this equation by the wavelength to get: >> >>Total energy = E*lambda = h*c = constant. >>--------------------------------------------------------------------------- >>What's a "complete wave"?

3 2

Re: [math-fun] What if Turing/Shannon/Bekenstein were wrong?
by Henry Baker 08 Apr '14

08 Apr '14

There is no length or space in anything you just mentioned, hence no wave _length_. You talked about only time & energy -- obviously complementary quantities, but no space. I'm interested in electromagnetic waves that propagate, and that involves space. Of course you're not going to find my interpretation in the standard textbooks; I wouldn't bother posting if I didn't think that there was some novel insight here. At 09:09 AM 4/8/2014, Eugene Salamin wrote: >The quantization of the electromagnetic field has nothing to do with any possible graininess to space; that would only be an issue for quantum gravity. > >An electromagnetic vibration can be resolved into normal modes. > >Each normal mode is a harmonic oscillator, and behaves exactly as a particle in a harmonic potential, or a mass on a spring. > >The energy levels are quantized: E[n] = (n + 1/2)hÎ½, where Î½ is the frequency. > >For the electromagnetic oscillator, when it has energy E[n], we say that there are n photons in that mode. > >The number of wavelengths that occur in the mode volume doesn't affect the energy. > >-- Gene > >>________________________________ >> From: Henry Baker <hbaker1(a)pipeline.com> >>To: Eugene Salamin <gene_salamin(a)yahoo.com>; math-fun <math-fun(a)mailman.xmission.com> >>Sent: Tuesday, April 8, 2014 8:50 AM >>Subject: Re: [math-fun] What if Turing/Shannon/Bekenstein were wrong? >> >>A single cycle of a wave; i.e., from 0 to 2pi. >> >>This is my whole point: one way of looking at the quantum nature of >>electromagnetic waves is that it hints at the graininess of space >>itself.Ã The wave is getting "sampled" by this grainy space into >>individual quanta. >> >>At 08:12 AM 4/8/2014, Eugene Salamin wrote: >>>> From: Henry Baker <hbaker1(a)pipeline.com> >>>>A single photon of an electromagnetic wave of wavelength lambda has energy E = h*c/lambda. >>>> >>>>The energy of a complete wave is computed by multiplying this equation by the wavelength to get: >>>> >>>>Total energy = E*lambda = h*c = constant. >>>>--------------------------------------------------------------------------- >>>>What's a "complete wave"?

1 0

[math-fun] bit-reverse meets OEIS, jj might keep his money
by Joerg Arndt 08 Apr '14

08 Apr '14

Here are my best strategies for reversing n-bit words: n a(n) == number of butterfly steps 0 0 1 0 2 1 [ 1, 1 ] 3 1 [ 1, 1, 1 ] 4 2 [ 2, 2 ] 5 2 [ 2, 1, 2 ] 6 2 [ 3, 3 ] 7 2 [ 3 1 3 ] 8 3 [ 4 4 ] 9 2 [ 3 3 3 ] 10 3 [ 5, 5 ] 11 3 [ 1, 9, 1 ] 12 3 [ 3, 3, 3, 3 ] 13 3 [ 6, 1, 6 ] 14 3 [ 7, 7 ] 15 3 [ 5, 5, 5 ] 16 4 [ 8, 8 ] 17 4 [ 8, 1, 8 ] 18 3 [ 9, 9 ] 19 3 [ 9, 1, 9 ] 20 4 [ 10, 10 ] [ 9, 1, 1, 9 ] 21 3 [ 9, 3, 9 ] 22 4 [ 9, 5, 9 ] [ 11, 11 ] 23 4 [ 9, 3, 3, 9 ] [ 11, 1, 11 ] 24 4 [ 8, 8, 8 ] [ 9, 3, 3, 9 ] 25 4 [ 5, 5, 5, 5 ] 26 4 [ 13, 13 ] 27 3 [ 9, 9, 9 ] 28 4 [ 7, 7, 7, 7 ] [ 14, 14 ] 29 4 [ 14, 1, 14 ] [ 9, 1, 9, 1, 9 ] 30 4 [ 10, 10, 10 ] 31 4 [ 5 X 3, 1, 5 X 3 ] 32 5 [ 16, 16 ] 33 4 [ 11, 11, 11 ] 34 5 [ 17, 17 ] 63 4 [ 27, 9, 27 ] 64 6 [ 32, 32 ] 81 4 [ 27, 27, 27 ] 243 5 [ 81, 81, 81 ] This coincides with http://oeis.org/A064415 a(1) = 0, a(n) = iter(n) if n is even, a(n) = iter(n)-1 if n is odd, where iter(n) = A003434(n) = smallest number of iterations of Euler totient function phi needed to reach 1. A064415 ,0,1,1,2,2,2,2,3,2,3,3,3,3,3,3,4,4,3,3,4,3,4,4,4,4,4,3,4,4,4,4,5,4,5,4,4,4,4,4,5,5,4,4,5,4,5,5, ... For all integers m >0 and n>0 a(m*n)=a(m)+a(n). The function a(n) is completely additive. The smallest integer q which satisfy the equation a(q)=n is 2^q, the greatest is 3^q. And apparently also with: http://oeis.org/A054725 a[1]=1; a[m]= sum[a[p-1]], where sum is over all primes (not necessarily distinct), p, that divide m. A054725 ,1,1,1,2,2,2,2,3,2,3,3,3,3,3,3,4,4,3,3,4,3,4,4,4,4,4,3,4,4,4,4,5,4,5,4,4,4,4,4,5,5,4,4,5,4,5,5,5, ... This one has a(0) "wrong". For your viewing pleasure, the 63 and 31 bit reversal routines that have the minimal number of butterfly steps: ulong jj3_revbin63(ulong x) // a(63) = 4 { ulong z; #if 1 z = (x ^ (x >> 2)) & 0x1249249249249249UL; x ^= z ^ (z << 2); // low 3 bits reversed z = (x ^ (x >> 6)) & 0x01c0e070381c0e07UL; x ^= z ^ (z << 6); // low 9 bits reversed z = (x ^ (x >> 18)) & 0x00001ff0000001ffUL; x ^= z ^ (z << 18); // low 27 bits reversed z = (x ^ (x >> 36)) & 0x0000000007ffffffUL; x ^= z ^ (z << 36); // low 63 bits reversed #else // same code using GCC's binary literals z = (x ^ (x >> 2)) & 0b0001001001001001001001001001001001001001001001001001001001001001UL; x ^= z ^ (z << 2); z = (x ^ (x >> 6)) & 0b0000000111000000111000000111000000111000000111000000111000000111UL; x ^= z ^ (z << 6); z = (x ^ (x >> 18)) & 0b0000000000000000000111111111000000000000000000000000000111111111UL; x ^= z ^ (z << 18); z = (x ^ (x >> 36)) & 0b0000000000000000000000000000000000000111111111111111111111111111UL; x ^= z ^ (z << 36); #endif // x = (x>>63) | (x<<1); // rotate left by 1 to have all 64 bits reversed return x; } uint jj3_revbin31(uint x) // a(31) = 4 as well! { uint z; #if 1 z = (x ^ (x >> 2)) & 0x12491249U; x ^= z ^ (z << 2); z = (x ^ (x >> 6)) & 0x00380038U; x ^= z ^ (z << 6); z = (x ^ (x >> 12)) & 0x00070007U; x ^= z ^ (z << 12); z = (x ^ (x >> 16)) & 0x00007fffU; x ^= z ^ (z << 16); #else // same code using GCC's binary literals z = (x ^ (x >> 2)) & 0b00010010010010010001001001001001U; x ^= z ^ (z << 2); z = (x ^ (x >> 6)) & 0b00000000001110000000000000111000U; x ^= z ^ (z << 6); z = (x ^ (x >> 12)) & 0b00000000000001110000000000000111U; x ^= z ^ (z << 12); z = (x ^ (x >> 16)) & 0b00000000000000000111111111111111U; x ^= z ^ (z << 16); #endif // x = (x>>31) | (x<<1); // rotate left by 1 to have all 32 bits reversed return x; } I'd be quite surprised to see anything better! Best, jj

1 2

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

07 Apr '14

1. So, far as I understand it (which I don't), Lunnon's latest (3rd) proof's key new idea, is that the points at knight-distance <=d to the origin, form a convex set, i.e. are precisely those within a certain convex region? His lemma 6? 2. (Incidentally, roughly that idea was in my head back when I devised my conjectural distance formula in first place.) 3. Using this lemma, one does not need to minimize over 8 choices, but rather over at most 4. 4. Unfortunately, the claim (1) above is false. So for that reason, plus several things in Lunnon's latest proof which literally make no sense (e.g. the statement of lemma 6 actually makes no sense as written in combination with defn 4) I'm sorry to report that I must again denounce this as a non-proof. On the bright side, however, the idea of (3) would be useful. Even if so, though, I think it's still going to be messy since although 4<8, we still have 4>1. Also, about Lunnon's calculation of "maximum number of shortest paths" finding "growth like d^2 * 2^d" I suspect an exact formula for this can be found using binomial coefficients and a finite number of cases.

2 1