July 2016 - mathfun@mailman.xmission.com

[math-fun] Draft of my July 2016 blog post
by James Propp 13 Jul '16

13 Jul '16

Hi, I started writing a new draft titled "The Man Who Knew Infinity: what the film will teach you (and what it won't)" and would love to get your feedback. I plan on publishing it on July 17. <x-apple-data-detectors://0> Please leave your feedback at https://mathenchant.wordpress.com?p=845&shareadraft=57855ac7ad9fa <https://mathenchant.wordpress.com/?p=845&shareadraft=57855ac7ad9fa> keeping in mind that the comments of EVERYONE on math-fun will get funneled through the same email conduit; if you want me to know who you are, please sign your comments! If you sign your comments I'll assume (unless you indicate otherwise) that you don't mind my acknowledging your contribution. Title: "The Man Who Knew Infinity": what the film will teach you (and what it won't) Beginning: During my years as a mathematician, not one film-maker has tried to teach me how to write better articles. So I'm not going to tell Matt Brown, the writer/director of “The Man Who Knew Infinity”, what he should or shouldn't have done in a movie that, as the fine print on the poster reminds us, is ba... Read more: https://mathenchant.wordpress.com?p=845&shareadraft=57855ac7ad9fa <https://mathenchant.wordpress.com/?p=845&shareadraft=57855ac7ad9fa> I appreciate candid criticism from people who share my aims but think I've fallen short of them. Thanks, Jim Propp

1 0

[math-fun] Math or mind-reading?
by Bill Gosper 13 Jul '16

13 Jul '16

Holt McDougal Mathematics Grade 7, Common Core Edition Chapter 2 Integers and Rational Numbers Lesson 2-4 Multiplying and Dividing Integers 60. What's the error? A student writes, "The quotient of an integer divided by an integer of the opposite sign has the sign of the integer with the greater absolute value." What was the student's error? [Answer: Majoring in English. In light of this shameful mistake the student's gender and ethnicity were withheld.] 17. Angelina hiked along a 2250-foot mountain trail. She stopped 5 times along the way to rest, walking the same distance between each stop. How far did Angelina hike before the first stop? [Was the start a stop?? If so, 0, If not, 2250/4. Or anything, really. Ah, the start was the 0th stop.] [Teacher: "Show your work."] 15. 63 / 0 30. -42 / 0 42. 0 / (- 3) [For the first two, I gave my student a large magnifier and suggested he burn holes through his answer sheet. But he thinks the answers should be 0 for no logical reason other than "That's what they wanted." Professor Edward Burger's accompanying video says the quotient should be negative if the signs differ. Since the sign of 0 differs from that of 63, the answer to #15 should be -0?] --rwg

1 0

[math-fun] computer word sizes of 2^2^n
by Bill Gosper 12 Jul '16

12 Jul '16

On 2016-07-06 07:13, Henry Baker wrote: > Is it just me, or does anyone else find this property pretty cool: > > (%i1) x^256-1,factor; > 2 4 8 16 32 64 128 > (%o1) (x - 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) > > I.e., the factors of 2^2^n-1 are (2^n-1) and (2^2^k+1) for k<n. > > This property has to be useful for some recursions on computer word > sizes, but I don't recall Knuth using it anywhere. > > Is anyone aware of *any* interesting use of this property? > It has to be prominent in Knuth (+Graham+Patashnik): it's the generating function of 1,1,1,1, ... and illustrates the uniqueness of binary notation: In[1727]:= Product[1 + x^2^n, {n, 0, ∞}] Out[1727]= 1/(1 - x) Closely related: In[1728]:= Product[Cos[t/2^n], {n, ∞}] Out[1728]= Sinc[t] --rwg The analysis of Karatsuba's multiplication speedup recurses on bisected word length. Or precision, anyway. https://en.wikipedia.org/wiki/Anatoly_Karatsuba pictures him as not the least Japanese, so the stress is on the TSU: Карацу́ба

4 3

Re: [math-fun] reversible computation; was 32-bit computers almost gone
by Henry Baker 11 Jul '16

11 Jul '16

I haven't followed the "reversible" research for several years now, but I think that this research somehow they got off on the wrong track to begin with, and never quite got back. In the '90's, the goal was to *lower* the energy dissipation, but not eliminate it (for reversible circuits). Thus, they did really slow logic, and some amount of charge recovery. But -- as you point out -- if you're using a highly non-linear device like a diode -- there are severe limits on what can be achieved. There needs to be some amount of non-linearity/error-correction in order to act as a refrigerator to reject the "heat" (in the form of noise) that intrudes into the computation. So we run into typical Maxwell's Demon issues. So we need to move to computational elements which are more isolated from the environment to begin with -- i.e., these computations are more "insulated" from the environment. It so happens that the requirements for reversible computation overlap those for quantum computations almost completely. After all, quantum computations are reversible, so they (using non-quantum modes) can emulate classical reversible computations. The real question is: if you have to do many of the same things for reversible computations as for quantum computations, then why not go directly to quantum computations -- which are strictly more powerful? That's probably why most non-quantum reversible computation research stopped a number of years ago. Now one aspect of reversible computation research hasn't (to my knowledge) been worked on very much: the emulation of complex reversible circuits using compositions of simpler reversible elements. Sooner or later, such compositions will be required for quantum computations, as well, but I guess much of this research has been tabled until actual quantum computers can be built. This is a pity, as it would be interesting to better understand the *synthesis* of complex reversible circuits from elementary reversible gates. Such an understanding may provide more insight into why certain reversible circuits are *hard to invert* -- e.g., encryption circuits. At 10:24 AM 7/6/2016, Richard Howard wrote: >1. Cheap means something different if you are talking about ubiquitous IOT nodes. > >Large amount of embedded memory are very expensive and external RAM chips >really break the bank for cost/size etc. > >Trend is to single chip solutions with MCU/radio/memory. Not compatible >with large quantities of DRAM. > >As to delta in linewidth--the news is that the end is near because we are >running out of atoms. Check the ITRS roadmap and Intel. > >I have a nice photo of a CMOS device with 142 atoms from source to drain >and 6 atoms of oxide (you can see the dots). > >That was 20 years ago in research--we are there on-schedule in production. > > 2. Sounds wonderful, but for IOT you need a processor with a very large >production run to get the cost down. Maybe someday SIMD single chip >solutions will be there, but not in the near term. > >3) Reversible computers are delightful ideas, but there are fundamental >issues running them at room temperature. > >Because of the kT/q slopes in diodes, you can't actually recover the >energy. Hardware was made 20 years ago and shows that nicely. >Now at mK temperatures, that is a different story. > >--R > >On Wed, Jul 6, 2016 at 11:48 AM Henry Baker <hbaker1(a)pipeline.com> wrote: > >> Yes, but... >> >> 1. Memory is cheap. Even uP will have decent sized memories. Every >> delta in line widths produces at least O(delta^2) in memory size, if not >> O(delta^3). >> >> 2. SIMD-type processors are cheap and quite energy-efficient. There's >> really no reason for a traditional 16-bit processor anymore. >> >> 3. Most crypto codes are 1-1 functions, and therefore *reversible*. In >> theory, reversible functions can be computed with asymptotically zero >> energy dissipation. >> >> At 07:31 AM 7/6/2016, Richard Howard wrote: >> >BTW, there is an interesting mathy problem here--how do you do security >> >when you have only a few microjoules and a few kB of memory in a 16 bit >> >processor? >> > >> >RSA is not even remotely feasible.

4 4

Re: [math-fun] computer word sizes of 2^2^n
by Henry Baker 11 Jul '16

11 Jul '16

This product of Fermat numbers in the discussion below made me think more about Fermat *relative* primes. According to Goldbach's *theorem* (not the conjecture), the Fermat numbers are all *relatively prime* to one another. https://en.wikipedia.org/wiki/Fermat_number Sooooo, the Chinese remainder theorem (CRT) can be used to represent integers mod each and all of the Fermat numbers. CRT arithmetic can be done in parallel, and in this instance it will be dominated by the computation mod the largest Fermat number -- in this case the one whose bits are half the word size. I seem to recall Knuth spending some time talking about clever ways to do arithmetic mod 2^n-1, but I don't recall if he discussed clever ways to do arithmetic mod 2^n+1. Somehow, you'd need a vector of extra bits, one per word. We've done this for ages with "tag bits" in various implementations of Lisp; perhaps similar techniques would work for 2^n+1 arithmetic. At 10:39 PM 7/6/2016, Bill Gosper wrote: >On 2016-07-06 07:13, Henry Baker wrote: >> Is it just me, or does anyone else find this property pretty cool: >> >> (%i1) x^256-1,factor; >> 2 4 8 16 32 64 128 >> (%o1) (x - 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) >> >> I.e., the factors of 2^2^n-1 are (2^n-1) and (2^2^k+1) for k<n. >> >> This property has to be useful for some recursions on computer word >> sizes, but I don't recall Knuth using it anywhere. >> >> Is anyone aware of *any* interesting use of this property? > >It has to be prominent in Knuth (+Graham+Patashnik): > >it's the generating function of 1,1,1,1, ... and illustrates the uniqueness of binary notation: > >In[1727]:= Product[1 + x^2^n, {n, 0, â}] > >Out[1727]= 1/(1 - x) > >Closely related: > >In[1728]:= Product[Cos[t/2^n], {n, â}] > >Out[1728]= Sinc[t] > >--rwg > >The analysis of Karatsuba's multiplication speedup recurses on bisected word length. > >Or precision, anyway. > >https://en.wikipedia.org/wiki/Anatoly_Karatsuba > >pictures him as not the least Japanese, so the stress is on the TSU: > >ÐÐ°ÑÐ°ÑÑÌÐ±Ð°

1 0

[math-fun] polyomino problem
by Erich Friedman 09 Jul '16

09 Jul '16

fix a positive constant k. consider a collection of polyominoes (located on the square grid) so that each n-omino is adjacent (along edges) to other polyominoes with total area kn. a little thought will convince you that: 1) when k=1, there are trivial solutions. 2) there are no examples unless k is an integer. 3) there are examples for arbitrarily large k. surprisingly, the solutions when k=2 have been completely classified by joe devincentis. the areas of the polyominoes involved in such a configuration have to be multiples of one of the following sets: {1}, {1,2}, {1,2,3}, {1,2,3,4}, or {1,2,3,4,5,6}. the proof is omitted, but the readers of this list should have no problem checking the various cases. the smallest known solutions (in terms of total area) for various values of k and various area sets are shown at the link below. improvements are welcome. http://www2.stetson.edu/~efriedma/mathmagic/0716.html <http://www2.stetson.edu/~efriedma/mathmagic/0716.html> is there any classification for k=3 as to what area sets are possible? when k=4, is there a solution using only 3- and 4-ominoes? it seems unlikely, but a proof has eluded me. what is the smallest solution (in terms of total area, or area set) for a given value of k? erich friedman

1 0

[math-fun] Never say never: stable 4-body system found in the 'wild'
by Henry Baker 08 Jul '16

08 Jul '16

FYI -- http://www.theverge.com/2016/7/7/12111660/exoplanet-three-suns-very-large-t… Massive planet found within a triple-star system It defies what researchers thought was possible More than 340 light years away, a giant planet is trapped in a dance with three stars. It's a unique world, where suns rise and set three times a day, and where one year lasts more than half a millennium. It's so bizarre that the existence of such a place was thought to be impossible Â but astronomers have captured a rare, direct picture of this exotic domain. ... That imaging paints a picture of a fairly unique world. HD 131399Ab is thought to be a gas giant, about four times the mass of Jupiter, with water and methane in its atmosphere. And its orbit is astonishing to the researchers. It travels around one of the stars in the system at a distance that's about twice that of the Sun and Pluto, an incredibly wide orbit that lasts 550 Earth-years. For most of that time, the planet has a routine daytime and nighttime, as the three suns rise and set close together. But as the planet moves throughout the system, there comes a time when one sun rises just as another sets. This leads to a period where HD 131399Ab is bathed in constant sunlight Â an interval that lasts 140 years. It's a scenario thatÂs never been seen before. Researchers suspected it was nearly impossible for a planet to have that wide of an orbit in a three-star system. It was thought that such a planet would be unstable, and that the gravity from the other stars would throw the planet off course and even eject it from the system entirely. But today's study reveals that such a set-up can actually exist, opening up the possibility that other similar systems exist elsewhere in the Universe. "That would have seemed like science fiction to us in the past," said Wagner.

1 0

[math-fun] UW, uSoft: big breakthrough with DNA data storage
by Henry Baker 08 Jul '16

08 Jul '16

FYI -- No doubt newborns will soon be screaming to be upgraded to Windows 10... http://www.seattletimes.com/business/microsoft/uw-microsoft-claim-big-break… A joint team from the Redmond company and the university said Thursday that it had successfully encoded about 200 megabytes of data onto synthetic DNA molecules Â nine times the previous record. Researchers from Microsoft and the University of Washington say theyÂve reached a milestone in the effort to use DNA to help store the worldÂs rapidly growing stash of digital data. A joint team from the Redmond company and the university said Thursday it had successfully encoded about 200 megabytes of data onto synthetic DNA molecules. The information, which the team later successfully decoded and read, included more than 100 books, translations of the Universal Declaration of Human Rights, and a high-definition music video from the band OK Go. ...

3 2

[math-fun] How I miss Mizan Rahman, or, what the heck is this?
by Bill Gosper 08 Jul '16

08 Jul '16

I haven't been following this discussion, but psi^4 is https://oeis.org/A008438 ("sum of divisors of 2n+1"), which is quite a long entry with many references and comments. If there's something new to add there, please add it (or tell me what to add)! Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com <http://neilsloane.com/> Email: njasloane(a)gmail.com Nothing much, except that it's the secret behind this obscure prime test: primeq[n_Integer]:=1==SeriesCoefficient[\[Integral](3 q^2+1/16 EllipticTheta[2,0,q]^4)\[DifferentialD]q/q,{q,0,n}] In[16]:= Select[Range@99,primeq] Out[16]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97} --rwg On Wed, Jul 6, 2016 at 11:37 PM, Mike Hirschhorn <m.hirschhorn(a)unsw.edu.au> wrote: Dear all, The right side is \psi(q)^4, where \psi(q) generates the triangular numbers, so the identity gives the number of reps of a number as the sum of 4 triangles, which must be well-known. Mike Hirschhorn. ________________________________ From: mathfuneavesdroppers(a)googlegroups.com < mathfuneavesdroppers(a)googlegroups.com> on behalf of Bill Gosper < billgosper(a)gmail.com> Sent: 07 July 2016 13:08:14 To: math-fun(a)mailman.xmission.com Subject: Re: How I miss Mizan Rahman, or, what the heck is this? George Andrews got it from Bailey's ??? transformation (rather than finding it scrawled on the wall of an ancient tomb.) Merely with elementary manipulations, starting with partial fractions, I reduced it to n q Sum[---------------, {n, -?, ?}] == 1 + 2 n 2 (1 - q ) 2 2 4 QPochhammer[q , q ] -------------------- 2 4 QPochhammer[q, q ] which is presumably known, since it's a simple q-extension of In[1653]:= Sum[(2 n - 1)^-2, {n, -?, ?}] Out[1653]= ?^2/4. Exercises: Evaluate 3 n + 1 q Sum[---------------, {n, -?, ?}] 1 + 2 n 2 (1 - q ) and n q Sum[------------, {n, -?, ?}] 1 + 2 n 1 - q Spoilers: 2 2 4 QPochhammer[q , q ] -------------------- 2 4 QPochhammer[q, q ] and 0 (off the unit circle). Problem: n integer, t real, L=Limit[sin nt,n->?]. Then L=0 or it doesn't exist? --rwg

2 1

Re: [math-fun] How I miss Mizan Rahman, or, what the heck is this?
by Bill Gosper 07 Jul '16

07 Jul '16

George Andrews got it from Bailey's ₂Ψ₂ transformation (rather than finding it scrawled on the wall of an ancient tomb.) Merely with elementary manipulations, starting with partial fractions, I reduced it to n q Sum[---------------, {n, -∞, ∞}] == 1 + 2 n 2 (1 - q ) 2 2 4 QPochhammer[q , q ] -------------------- 2 4 QPochhammer[q, q ] which is presumably known, since it's a simple q-extension of In[1653]:= Sum[(2 n - 1)^-2, {n, -∞, ∞}] Out[1653]= π^2/4. Exercises: Evaluate 3 n + 1 q Sum[---------------, {n, -∞, ∞}] 1 + 2 n 2 (1 - q ) and n q Sum[------------, {n, -∞, ∞}] 1 + 2 n 1 - q Spoilers: 2 2 4 QPochhammer[q , q ] -------------------- 2 4 QPochhammer[q, q ] and 0 (off the unit circle). Problem: n integer, t real, L=Limit[sin nt,n->∞]. Then L=0 or it doesn't exist? --rwg On Sat, Jul 2, 2016 at 11:19 AM, Bill Gosper <billgosper(a)gmail.com> wrote: > Out[1131]= > k > q > Sum -------------------------------, > 1 - 2 k 2 1 + 2 k 2 > (1 - q ) (1 - q ) > k,-∞,∞ > > = > 1 2 4 > (1 + q) QFactorial[-(-), q ] > 2 > ----------------------------- > 2 4 > (1 - q ) > > q-Pochhammers in the sum but not the summand? "q-Mittag Leffler"? > > It q-retracts to > 16 > Sum[-----------, {k,-∞,∞}] == > 2 2 > (1 - 4 k ) > 2 > 2 π > > Mathematica is dumbstruck. For minutes on end. > Are these actually common? > > Test for q=1/2: > In[1132]:= N[Activate[%1131/.q->.5]] > Out[1132]= True > > Term ratio: > In[1180]:= DiscreteRatio[%1131[[1,1]],k] > Out[1180]= (q (1-q^(1-2 k))^2 (1-q^(1+2 k))^2)/((1-q^(-1-2 k))^2 (1-q^(3+2 > k))^2) > > Nine terms of the sum give 27 term agreement with the product, despite the > lack > of q^k²: > > In[1189]:= > Series[%1131/.\[Infinity]->9/.-\[Infinity]->-9//Activate,{q,0,29}] > Out[1189]= 1+5 q+12 q^2+24 q^3+44 q^4+68 q^5+102 q^6+150 q^7+202 q^8+270 > q^9+354 q^10+446 q^11+561 q^12+693 q^13+838 q^14+1002 q^15+1195 q^16+1407 > q^17+1638 q^18+1906 q^19+2179 q^20+2491 q^21+2842 q^22+3202 q^23+3610 > q^24+4042 q^25+4504 q^26+5008 q^27+5549 q^28+6114 q^29+O[q]^30==1+5 q+12 > q^2+24 q^3+44 q^4+68 q^5+102 q^6+150 q^7+202 q^8+270 q^9+354 q^10+446 > q^11+561 q^12+693 q^13+838 q^14+1002 q^15+1195 q^16+1407 q^17+1638 > q^18+1906 q^19+2179 q^20+2491 q^21+2842 q^22+3202 q^23+3610 q^24+4042 > q^25+4504 q^26+5008 q^27+5550 q^28+6114 q^29+O[q]^30 > > In[1190]:= Subtract@@% > Out[1190]= -q^28+O[q]^30 > > I got it by mildly abusing the (bilateral) "q-Dixon's theorem" in > http://math.sun.ac.za/~hproding/pdffiles/Triples-long.pdf > which is not the (unilateral) q-Dixon's I get from path invariant > matrices. --rwg >

3 2