May 2013 - mathfun@mailman.xmission.com

[math-fun] Progress in Solving the Weak Twin-Prime Conjecture
by Hans Havermann 16 May '13

16 May '13

"The new result, by Yitang Zhang of the University of New Hampshire in Durham, finds that there are infinitely many pairs of primes that are less than 70 million units apart without relying on unproven conjectures." http://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-c…

3 2

[math-fun] Has anyone seen this construction before?
by Mike Stay 15 May '13

15 May '13

A *comatrix* consists of three sets X, Y, and S, and two functions f:X -> S, g:Y -> S. We can define composition of comatrices A=(X,Y,S,f,g) and B=(Y,Z,T,h,j) by B o A = (X, Z, (T+S)/g(y)~h(y), f, j). I made up the name above. Does anyone know this construction under a different name? I suspect it might be used in dealing with sparse matrices somewhere, since when all the sets are finite, g x h:Y -> S x T can be thought of as a matrix where the (s,t) element is the size of the preimage of (s,t) under g x h. Then (T+S)/g(y)~h(y) is a measure of how many nonzero elements there are. -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

2 1

[math-fun] The ternary Goldbach conjecture proven
by Hans Havermann 14 May '13

14 May '13

Harald Helfgott has a (lengthy) argument proving that every odd number greater than five is the sum of three primes. http://arxiv.org/abs/1305.2897

1 0

Re: [math-fun] "memoization"; considered harmful
by Bill Gosper 13 May '13

13 May '13

Cris Moore <moore(a)santafe.edu> wrote: Of course, "memoization" is a silly neologism, redolent of 1950's office work ;-) Only for the elderly. when I teach this subject, I use the perfectly good word "memorization". Indeed. "Memoization" has never achieved full cromulence, in my book. I've never had a problem with just "caching" results. Phil [Carmody] --------- I agree it's ugly. I disagree that it's superfluous. Foisting its meaning onto "memorizing" and "caching" overloads them and deprives them of connotation, so I fear we're stuck with "memoizing". Which when typed into Mathematica's Help dialog will soon find you tutorial/FunctionsThatRememberValuesTheyHaveFound [...] "There is of course a trade-off involved in remembering values. It is faster to find a particular value, but it takes more memory space to store all of them. You should usually define functions to remember values only if the total number of different values that will be produced is comparatively small, or the expense of recomputing them is very great." This is an understatement on a par with "Caution: Cigarette Smoking May be Hazardous to Your Health" (1966–1970). The performance degradation increases steeply and linearly as the cache grows, rapidly becoming prohibitive. E.g., the exact Hilbert spacefilling function Clear[Hilbert]; Hilbert[t_, a1_: 1, a0_: 0] := Hilbert[t, b1_: 1, b0_: 0] = (Hilbert[t, s1_: 1, s0_: 0] = ((a0 - s0)/(s1 - a1)); Module[{t4 = 4*t, n}, n = Floor[t4]; t4 -= n; Switch[n, 0, I*(1 - Hilbert[1 - t4, -I*a1/2, a0 + a1*I/2])/2, 1, (I + Hilbert[t4, a1/2, a0 + a1*I/2])/2, 2, (1 + I + Hilbert[t4, a1/2, a0 + a1*(1 + I)/2])/2, 3, 1 + I*Hilbert[1 - t4, a1*I/2, a0 + a1]/2, 4, 1]]) actually requires memoizing to find the fixed point of infinite recursions: In[280]:= Hilbert/@Range[0, 1, 1/6] Out[280]= {0, 1/2 + I/2, I, 1/2 + I/2, 1 + I, 1/2 + I/2, 1} Note how 1/6, 1/2, and 5/6 all map to the center of the target square [0,1]×[0,i]. So we can draw an "nth order Hilbert curve" as a polygon joining the centers of the 4^n subsquares of [0,1]×[0,i], whose inverse images are {c,c+1,c+2,...,c+4^n-1}/4^n, for c=1/6, 1/2, or 5/6. (3^4^n choices.) For a pretty but traditional picture, (choosing c=1/2) try Timing[Graphics[ Polygon[{Re[#], Im[#]} & /@ Join[{1, 0}, Hilbert /@ Range[4^-3/2, 1, 4^-3]]]]] {0.027261,...} Immediately rerunning this gave a timing of 0.004007, thanks to memoizing. This choice c=1/2 restricts the calculation to dyadic rationals, permitting a much simpler, non-memoizing, non-fixed-pointing Hilbert with termination conditions just for 0 and 1. But what's not to like? Memoizing is working fine. (Digression, for a non-traditional, non-dyadic-rational plot that really needs memoizing, try, e.g., Graphics[Polygon[{Re[#],Im[#]}&/@Append[Hilbert/@Range[4^-6,1,5/2^11],1]]]) But when Neil tried an 8th order dyadic curve, it would not finish. Even after supper. Clearing and redefining Hilbert, a mere 6th order curve took In[25]:= Timing[Do[Hilbert[k], {k, 4^-6/2, 1, 4^-6}]] Out[25]= {106.747152, Null} That's the same number of points (4^6) as one quarter of a 7th order: In[27]:= Timing[Do[Hilbert[k], {k, 4^-7/2, 1/4, 4^-7}]] Out[27]= {336.662000, Null} which takes > thrice as long! Since Neil only needed the c=1/2 dyadic case, he disgustedly wrote a finite state machine (two bits of t in, one bit each of x and y out). But let us grimly proceed. The 2nd quadrant of 7th order, In[32]:= Timing[Do[Hilbert[k], {k, 1/4 - 4^-7/2, 1/2, 4^-7}]] Out[32]= {394.267917, Null} is even slower, but should have been faster due to cached values from the first quadrant! Try something drastic--clear the cache and redefine the whole function for every point: In[33]:= Timing[ Do[Clear[Hilbert]; Hilbert[t_, a1_: 1, a0_: 0] := Hilbert[t, b1_: 1, b0_: 0] = (Hilbert[t, s1_: 1, s0_: 0] = ((a0 - s0)/(s1 - a1)); Module[{t4 = 4*t, n}, n = Floor[t4]; t4 -= n; Switch[n, 0, I*(1 - Hilbert[1 - t4, -I*a1/2, a0 + a1*I/2])/2, 1, (I + Hilbert[t4, a1/2, a0 + a1*I/2])/2, 2, (1 + I + Hilbert[t4, a1/2, a0 + a1*(1 + I)/2])/2, 3, 1 + I*Hilbert[1 - t4, a1*I/2, a0 + a1]/2, 4, 1]]); Hilbert[k], {k, 4^-7/2, 1, 4^-7}]] Out[33]= {18.388266, Null} for all four quadrants! I can't believe WRI can't easily, dramatically remediate this. Neil made some damning running-time plots which I hope he will blog soon. --rwg (Saving and resuming this draft introduced many redundant line breaks. Apologies if GMail has undeleted them.)

4 3

Re: [math-fun] Anyone who fell in would die
by Keith F. Lynch 13 May '13

13 May '13

Bill Gosper <billgosper(a)gmail.com> wrote: > In all these intervening centuries, has no one thought of anchoring > a(n unpowered) skiff with a tiller on a long rope running upstream? > With ropes to both shores in case you find it not on your departure > side. I thought that was the standard way of running a river ferry before steam engines were invented: A fixed cable across the river, and a tiller to use the current to push the ferry (which is permanently attached to the cable, but free to move along its length) to one side of the river or the other.

1 0

[math-fun] A plant with almost zero "junk DNA"
by Warren D Smith 13 May '13

13 May '13

http://www.nature.com/nature/journal/vaop/ncurrent/full/nature12132.html only 3% of its DNA is junk.

1 0

[math-fun] Hilbert(Hilbert)
by Bill Gosper 12 May '13

12 May '13

Tonight, after a couple of weeks of work, Neil produced http://gosper.org/hilbert.png . This is *way* harder that Peano(Peano) or Gosper(Gosper). --rwg

5 5

[math-fun] Anyone who fell in would die
by Bill Gosper 11 May '13

11 May '13

http://www.reddit.com/r/videos/comments/1dqcbf/how_to_cross_a_river_with_tw… This much current could be converted to an asset. River fording is an ancient, universal problem. In all these intervening centuries, has no one thought of anchoring a(n unpowered) skiff with a tiller on a long rope running upstream? With ropes to both shores in case you find it not on your departure side. --rwg

1 0

[math-fun] Current status of Mochizuki's claimed proof of the ABC Conjecture?
by Marc LeBrun 10 May '13

10 May '13

Haven¹t seen anything here since last September but someone at work randomly brought this up so thought I¹d ask: What is the current status of Mochizuki's claimed proof of the ABC Conjecture?

3 2

[math-fun] z^n = 1 for Gaussian integer n
by Kerry Mitchell 10 May '13

10 May '13

Hi all, I am playing with a problem that has boiled down to this: for positive integer n, there are n complex roots of 1 (or any complex number). What happens when n is a Gaussian integer? How many roots are there and what are they like? I've done some preliminary work on this; can someone point me to a reference so I can see if I'm on the right track? Thanks, Kerry

5 11