April 2015 - mathfun@mailman.xmission.com

[math-fun] A Data-Driven Exploration of the Evolution of Chess
by Ray Tayek 11 Apr '15

11 Apr '15

http://games.slashdot.org/story/15/04/09/2228218/a-data-driven-exploration-… -- Honesty is a very expensive gift. So, don't expect it from cheap people - Warren Buffet http://tayek.com/

1 0

[math-fun] SSA congruence
by James Propp 10 Apr '15

10 Apr '15

Back about 30-40 years ago, I posed a problem in Mathematics Magazine (or maybe the Monthly) asking whether any triangle could be linked to a non-congruent similar triangle via a sequence of triangles, each "SSA-congruent" to the one before and the one after. There was a cute solution that pointed out that this is impossible because two SSA-congruent triangles have the same X, where X was some triangle statistic (like perimeter, inradius, or circumradius, but slightly less well-known) that scales linearly under similarity. Can anyone (a) figure out what X was, or (b) locate my problem and the solution? Jim Propp PS: In my original submission I proposed the term "ASS-congruent", which struck me as both more pronounceable and more apt, but the stodgy problems editor who reigned at the time deemed this too vulgar.

11 21

Re: [math-fun] Moire patterns
by James Propp 10 Apr '15

10 Apr '15

For a fun time (or maybe a headache), point your browser at http://www.nap.edu/openbook.php?record_id=2267&page=115 and then jiggle your scrollbar up and down. Then stop. Then jiggle. Then stop. Then jiggle. Can anyone explain to me what's going on in one's visual system when one does this? Jim Propp On Thu, Apr 9, 2015 at 11:41 PM, James Propp <jamespropp(a)gmail.com> wrote: > Three years ago, Dan Asimov wrote (as part of a math-fun thread with the > subject line "big sunflowers"): > > I was also about to mention the same book. >> >> In fact, the author, Isaac Amidror, has written >> a second volume, "The theory of the Moiré phenomenon. Vol. II" >> as well as a 2nd edition of the first volume, now called >> "The theory of the Moiré phenomenon. Vol. I". >> >> According to Math Reviews, these are considered the definitive >> reference on the Moiré phenomenon. >> >> Also, the same guy has coauthored a recent paper: >> >> Isaac Amidror & Roger D. Hersch (2010): Mathematical moiré models and >> their limitations, Journal of Modern Optics, 57:1, 23-36, >> >> which I have downloaded and which looks quite readable. > > > I still haven't gotten around to looking at Amidror's book, but I did look > at the online table of contents at http://diwww.epfl.ch/w3lsp/books/moire > /prefaceKluwer.html (thanks, Thane!), and I also leafed through Amidror's > article with Hersch, and one thing that frustrated me was the apparent > absence of a framework for limit-objects. > > I was expecting that, just as there are graphons in graph theory and > varifolds in geometric measure theory, there'd be some sort of > limit-objects that ordinary Moire pattern pictures converge toward (though > perhaps one would want various notions of convergence here, depending on > what features of the Moire patterns one wishes to understand in the limit). > > As far as I can tell, Amidror has no interest in devising such an artsy > 20th/21st century infrastructure; he just gets his hands dirty in the > details of specific Moire patterns, using Fourier theory in a very 19th > century way. (But I've only skimmed; maybe I'm missing key features of > Amidror's approach.) > > I'd be interested in more abstract approaches to the question "In what > sense do Moire patterns converge?", since they'd be relevant to things like > the Abelian Sandpile Model and the Rotor-Router Model that I think about > from time to time; for such models one sees a variety of effects at a > variety of scales, with mesoscopic effects that are quite different from > both the macroscopic effects and the microscopic effects, and it's a > challenge to devise the right language in which one might describe these > effects and formulate conjectures, let alone prove things. > > Jim Propp >

3 4

Re: [math-fun] Unusual ways to count thru all w-bit numbers
by Warren D Smith 10 Apr '15

10 Apr '15

> From: Mike Stay <metaweta(a)gmail.com> > Klimov and Shamir have a few papers on what they call "T-functions" > and describe cheap ones with maximal period. > > "In particular, we show that for any n the mapping x ? x + (x? ? C) > (mod 2?) is a permutation with a single cycle of length 2? iff both > the least significant bit and the third least significant bit in the > constant C are 1." > > http://www.wisdom.weizmann.ac.il/~ask/ A.Klimov+A.Shamir (their theorem 3): The mapping x --> x + ((x^2) OR C) using mod 2^w arithmetic, is a permutation of length 2^w, i.e. consisting of a single cycle, iff the least-significant and third-least-significant bit of the constant C both are 1. The foremost example would be C=5, and they tried that with W=64 bit long words, finding the top 32 bits of each word passed the NIST pseudorandomness test suite. Nice theorem. However, this function still features "unidirectional info flow" on its bits, hence is a poor psu-random number generator, despite whatever Klimov+Shamir say to the contrary. And the NIST suite has very basic tests only, it is not a serious hurdle like the TestU01 suite. But I do not need any suite at all to see this violates my own obvious randomness test since the lower-signif bits have lower periods. On the other hand the unidirectional info flow property makes it far easier to prove theorems like theirs -- their immense verbiage obscures this simple idea which lies behind all the proofs by both them and many others. (Furthermore, the same idea but thinking mixed-radix rather than binary, enables proving most of the other full-period theorems out there working mod M for other moduli M besides powers of 2.) Another paper by Klimov+Shamir remarks that x --> x + 1 + 4*x*x (mod 2^W) yields a single cycle and may be computed using only 2 machine instructions, one to compute y=x*x, the other to compute x+1+4*y using the x86 "lea" (load effective address) instruction. Bet your compiler won't realize that. The x + ((x^2) OR C) took 3 instructions, which your compiler probably will realize. They say a polynomial map x --> FixedPolynomial(x) (mod 2^W) for W>3 yields a single cycle iff it has a single cycle modulo 8, i.e. works for W=3. A lovely theorem. They claim a fraction 1/64 of random polynomials obey that. They then move on to iterations with vector state, i.e. not just one word. For example the map on 4-vectors of W-bit machine words [x0,x1,x2,x3] --> [x0 XOR s XOR (2*x1*x2), x1 XOR (s AND a0) XOR (2*x2*x3), x2 XOR (s AND a1) XOR (2*x3*x0), x3 XOR (s AND a2) XOR (2*x0*x1) ] they say will yield a single cycle of full length 16^W where a0=x0, a1=a0 AND x1, a2=a1 AND x2, a3=a2 AND x3, s=(a3+C) XOR a3, and C is any odd constant. They have several other examples and they can be implemented to run at very high speeds by using some SSE machine language tricks. It is possible to somewhat disguise the low-period poor behavior of low-signif bits produced by these and other such iterations, by not using their outputs X directly, but rather using f(X), for some appropriately-chosen bijective "clean up function" f(X). A disguise based on XORing various bits, for example, could be used, but good randomness tests such as bit-matrix rank tests should be able to see though such a disguise. A harder disguise to penetrate might be something like "reverse the order of X's bits to get Y, then output a bijective quadratic function of Y."

3 3

Re: [math-fun] Project Durin Succeeds! (KF Lynch)
by Keith F. Lynch 10 Apr '15

10 Apr '15

Warren D Smith <warren.wds(a)gmail.com> wrote: > --well, storing over 50 bits in a tuning fork frequency is absurd, > for one thing... I never suggested storing 50 bits in a tuning fork frequency. Indeed, I pointed out how absurd that was. My idea was one large tuning fork to get the sphere noticed, and lots of small ones to convey a short message. I don't know enough about sound propagation in rock, or about the relevant signal-to-noise ratios, to know how high a frequency could be used. I do know that if the wavelength isn't much larger than the size of the mineral grains, the sound will be scattered, like light in a fog. But if the S/N ratio is good enough, a fair amount of scattering and absorption can be tolerated, since there's no limit to how much a receiver can amplify a signal. > --I am unconvinced. It is not mathematically possible for any lone > body to be "captured" into a high earth orbit, so any would have to > have been there since formation. It's just as possible for a body to be captured as for it to be ejected. It can happen from interactions with the Moon, from collisions near Earth, or from outgassing (e.g. comet remnants). Once it's captured, tidal drag can circularize the orbit, and can either raise or lower a circular orbit. It's believed that Mars' two small moons are captured asteroid or comet remnants, as are the smaller moons around the outer planets. > Also if KFL is correct, then I ask him: where are the tiny > satellites of Venus? Good question. The answer probably involves either the Sun's high tidal effect (2.6 times that on Earth) or Venus' very slow rotation or both. Also, stuff in solar orbit with any given aphelion will have a much higher speed relative to the inner planets when in the vicinity of those planets, making capture more difficult. > "Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: >> The Voyager records are expected to remain playable for at least >> 10 billion years, which is a respectable amount of time even by my >> standards. > --but you were claiming my 2 cm thick dust estimate was way too > small, which seems like it would contradict this? Interstellar space, which the Voyager probes are entering, is much, much emptier than our solar system. Anyhow, I'm not sure what you think the 2 centimeters of lunar dust is a measure of, other than itself. > --the moon may have formed for a few km of rocks of all sizes in > top, already there at formation, not due to meteors. And then, > after that short era of formation and initial blasting ended, then > the rest of time (several Gyr) only sufficed to cause 2cm of dust > to form on top of all that, in most places. No, the bombardment is still ongoing. It has slowed since the early days of the solar system, but it's far from over. The Apollo seismometers recorded plenty of natural impacts. > If so, indicating decent chance of multi-Gyr survival in space (if > willing to sacrifice a few cm thick outer layer) might be feasible. In solar orbit? It's possible. There are reasonably stable solar orbits, but they're mostly high in debris. However, debris impacts won't just erode the surface; they are likely to either shatter the message probe or knock it into an unstable orbit, i.e. an orbit in which its eccentricity will be pumped up by Jupiter until it hits a planet, plunges into the sun, or is ejected from the solar system. Even if it survives in good condition, how would anyone ever find it and recognize it as artificial? The solar system is very large and contains lots of debris. In interstellar space, as I said, pristine survival is highly likely but anyone ever finding the message probe is all but impossible. > It's an interesting idea, but clearly neither one of us has thought > it through enough. Yes. I need to know more geology, more about sound propagation in rock, and more about how materials behave at high temperatures and pressures for long periods. > (Also, are aliens really going to work that hard to leave a Gyr > message for us? Why should they want to?) Because it's a lot cheaper and easier than pointing a huge radio dish at us and transmitting for a billion years? But people spend time and effort listening for such messages. > If "Durin" aliens were going to make meter-size titanium balls and > land them on Earth, it would seem easier for them to do other stuff > instead that'd work better. What do you think would work better? I was envisioning spheres about an order of magnitude larger than that. Pressure vessels scale linearly, i.e. if a one-meter sphere requires a ten-centimeter-thick wall, then under the same pressure a ten-meter sphere would require a one-meter-thick wall. But that assumes uniform pressure in all directions, which may be far from the case in rock. I don't know. I wonder if anyone does. Bill Gosper <billgosper(a)gmail.com> wrote: > Stromatolite junk DNA? How do you prevent random mutations from accumulating over the ages?

1 0

[math-fun] Moire patterns
by James Propp 10 Apr '15

10 Apr '15

Three years ago, Dan Asimov wrote (as part of a math-fun thread with the subject line "big sunflowers"): I was also about to mention the same book. > > In fact, the author, Isaac Amidror, has written > a second volume, "The theory of the Moiré phenomenon. Vol. II" > as well as a 2nd edition of the first volume, now called > "The theory of the Moiré phenomenon. Vol. I". > > According to Math Reviews, these are considered the definitive > reference on the Moiré phenomenon. > > Also, the same guy has coauthored a recent paper: > > Isaac Amidror & Roger D. Hersch (2010): Mathematical moiré models and > their limitations, Journal of Modern Optics, 57:1, 23-36, > > which I have downloaded and which looks quite readable. I still haven't gotten around to looking at Amidror's book, but I did look at the online table of contents at http://diwww.epfl.ch/w3lsp/books/moire /prefaceKluwer.html (thanks, Thane!), and I also leafed through Amidror's article with Hersch, and one thing that frustrated me was the apparent absence of a framework for limit-objects. I was expecting that, just as there are graphons in graph theory and varifolds in geometric measure theory, there'd be some sort of limit-objects that ordinary Moire pattern pictures converge toward (though perhaps one would want various notions of convergence here, depending on what features of the Moire patterns one wishes to understand in the limit). As far as I can tell, Amidror has no interest in devising such an artsy 20th/21st century infrastructure; he just gets his hands dirty in the details of specific Moire patterns, using Fourier theory in a very 19th century way. (But I've only skimmed; maybe I'm missing key features of Amidror's approach.) I'd be interested in more abstract approaches to the question "In what sense do Moire patterns converge?", since they'd be relevant to things like the Abelian Sandpile Model and the Rotor-Router Model that I think about from time to time; for such models one sees a variety of effects at a variety of scales, with mesoscopic effects that are quite different from both the macroscopic effects and the microscopic effects, and it's a challenge to devise the right language in which one might describe these effects and formulate conjectures, let alone prove things. Jim Propp

1 0

Re: [math-fun] math-fun Digest, Vol 146, Issue 19
by Leo Broukhis 09 Apr '15

09 Apr '15

On Wed, 8 Apr 2015 12:53:47 +0200, Joerg Arndt <arndt(a)jjj.de> wrote: > Don't essentially all existing platforms(*) just treat > signed "int"s as what they are: fixed length registers? > I know only of Itanium where overflow may trap (not even > sure if it's the default there, at least I got no warnings > and no traps the single time I used Itanium). All *contemporary* existing platforms likely do. There used to be platforms where integers were essentially denormalized floating point numbers. A non-trapping integer overflow (yielding a normalized floating point number) would not be equal to any integer, and an attempt to perform bitwise Boolean operations on it would result in garbage. My understanding is that the proximate rationale for making integer overflow undefined behavior is DSP-like CPUs which might have saturating integer overflow by default; thus int a = 1; while (a != 0) a = a+1; is indeed an infinite loop. Teaching people not to use signed integers when they need modulo 2^w operations or bitmask manipulation is a good thing. Leo

2 1

[math-fun] That fractal pentagram again
by Bill Gosper 09 Apr '15

09 Apr '15

For some pictorial. mildly trick questions: http://gosper.org/foupent.pdf (1.6M) --rwg

1 4

[math-fun] length of earth day
by dupre＠math.rutgers.edu 09 Apr '15

09 Apr '15

I noticed in the Scientific American article linked to in item 4 of vol 146 #18, the common error was made of saying that the length of the earth day was the time it took the earth to rotate once on its axis. If the earth kept the same face to the sun, it would still rotate once on its axis in a year. Thus the earth rotates 366.2425 times on its axis in a year. The length of a day could be defined by drawing a ray from the center of the earth through the center of the sun. Think of this ray as being affixed to the earth. As the earth rotates around its axis, in about 24 hours, this ray will come closest to the center of the sun again. This is one day. Through how many degrees does the earth rotate on its axis in a day? (365.2425)/(366.2425) times 360 = 359.02 degrees in a day.

2 1

[math-fun] Unusual ways to count thru all w-bit numbers
by Bill Gosper 08 Apr '15

08 Apr '15

WDS>To FWL: "Unidirectional" info flow implies that the low-signif bits of x, have tiny periods, namely the (<=K)th bits have period <=2^(K-1). This behavior is just like the boring repeated-increment counter. If you want to avoid that boredom, you need bidirectionality. Incidentally, another counter for word length W=16 is x=0; do{ x = (x+1)*75 mod (2^16+1) - 1; }until(x=0); The sorts of "bidirectional bit flow" counters I described before are quite fast, but unfortunately rather expensive to find. (They are fast once found.) In fact the only ways I know to find them take about 4^W operations (heuristically). <WDS For n0ught else but DFT, can't modern CPUs reverse bits? The AILab PDP6 could. (And more: CIRC instruction.) Rich used it to count the 5x5 magic squares. And Knuth's proposed 64bit matrix instructions reverse bits. So the xor of a unidirectional and the bit-reverse of another one should do nicely. But probably just mixing a CIRC in with the counting instructions will produce some serious noise. --rwg

1 0