April 2013 - mathfun@mailman.xmission.com

Re: [math-fun] Kenneth I. Appel, Mathematician Who Harnessed Computer Power, Dies at 80
by Keith F. Lynch 30 Apr '13

30 Apr '13

David Makin <makinmagic(a)tiscali.co.uk> wrote: > I meant such that the "countries" are volumes not surfaces - > and I suspect the answer is 5 (based on change from triangle > to tetrahedron). No, the answer is unbounded. For instance let each 3D country consist of a wide horizontal plate with a long vertical rod attached. You can stack any number of plates, and they all touch each other. (The plates have holes just big enough for the rods to snugly fit through.) But I wonder what the answer is if the countries are constrained to be convex. Probably still unbounded, given that all graphs are embeddable in three-space, but my geometric intuition isn't good enough to be sure of this.

2 1

Re: [math-fun] ridiculously simple derivation (whose?) of Pythagorean triples
by Henry Baker 30 Apr '13

30 Apr '13

Bumby! Excellent! Just exactly what I wanted. Thanks, Neil! http://www.math.rutgers.edu/~bumby/squares1.pdf At 06:26 AM 4/29/2013, Neil Sloane wrote: >Entry A000118 in the OEIS has many references. See, in particular, the Bumby reference. > >On Mon, Apr 29, 2013 at 9:14 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> I'm still on the hunt for a 'ridiculously simple' way to express a positive integer as 4 squares. >> >> Most presentations for the 4-square theorem focus on proving that it is possible, but don't provide very good algorithms for actually doing it. >> >> At 09:47 AM 4/26/2013, Dan Asimov wrote: >>>How does that work with quaternions H or octonions O ? >>> >>>You can't just switch one coefficient. (Or you can, but >>>then you're just operating in a single complex subspace >>>of H or O, so it's really the same thing.) >>> >>>--Dan >>> >>>On 2013-04-26, at 5:50 AM, Fred lunnon wrote: >>> >>>> Etc. for quaternions and octonions, where available ... WFL >>>> >>>> On 4/26/13, Warut Roonguthai <warut822(a)gmail.com> wrote: >>>>> I don't know who discovered this, but I know that Pythagorean triples can >>>>> be obtained from the fact that |z^2| = |z|^2. This is similar to the way >>>>> you can prove that the product of numbers representable as sums of two >>>>> squares is also representable as a sum of two squares by using the fact >>>>> that |z1 * z2| = |z1| * |z2|. >>>>> >>>>> On Fri, Apr 26, 2013 at 3:04 PM, Bill Gosper <billgosper(a)gmail.com> wrote: >>>>> >>>>>> In[570]:= (1+2*I)/(2+1*I) >>>>>> Out[570]= 4/5+(3 I)/5 >>>>>> >>>>>> In[571]:= (1+3*I)/(3+1*I) >>>>>> Out[571]= 3/5+(4 I)/5 >>>>>> >>>>>> In[572]:= (2+3*I)/(3+2*I) >>>>>> Out[572]= 12/13+(5 I)/13 >>>>>> >>>>>> In[573]:= (1+4*I)/(4+1*I) >>>>>> Out[573]= 8/17+(15 I)/17 >>>>>> >>>>>> In[586]:= Simplify/@ComplexExpand[(a+I*b)/(b+I*a)] >>>>>> Out[586]= (2 a b)/(a^2+b^2)-(I (a^2-b^2))/(a^2+b^2) > >-- >Dear Friends, I have now retired from AT&T. New coordinates: > >Neil J. A. Sloane, President, OEIS Foundation >11 South Adelaide Avenue, Highland Park, NJ 08904, USA >Phone: 732 828 6098; home page: http://NeilSloane.com >Email: njasloane(a)gmail.com

2 1

Re: [math-fun] 4cc
by Richard Guy 29 Apr '13

29 Apr '13

Yes, Frank Allaire it was. And I think he came from Waterloo, where some other leading contributors to 4CC were based. R. On Mon, 29 Apr 2013, Victor Miller wrote: > Dear Richard, You said > > Dear All, > At about the time that A & H did their stuff, I had a > post-doc (at my age names disappear) who was working independently > on the 4CC. A & H beat him by several months, but this chap's > decomposing (?? again, can't rememember the word) system was > somewhat more efficient than A & H's, so that his machine time > was only about half of their's. > > Incidentally, in connexion with the argument as to > whether it's a proof or not, this independent arrival of the > result dispels a good deal of the doubt. R.[cleardot.gif] > > > Was it Frank Allaire? One of my close friends (Daniel IA Cohen) had done > his Harvard Ph.D. in 1975 about the 4cc. He was in correspondence with > Frank Allaire (I believe) who was at some Canadian University (I thought it > was Waterloo, but I could be wrong). He was collaborating with a fellow > named Swart. Somewhere in my files I have some of his writeups. > > > Best, > > Victor > > >

1 0

[math-fun] Kenneth Appel ...
by Guy Haworth 29 Apr '13

29 Apr '13

Sad news indeed ... but his work lives on, and fascinating it was. To work out what 1,200 hours of 1976 computing is today, maybe one can just divide by four for every three years, so that's *0.25^12 ... or less than one second. However, the algorithm admitted of 'embarrassing parallelism' whereby many independent parts of the proof (one for each subsetted subgraph) could be carried out in parallel. So, one need not wait even one second if there's a hurry on! Guy

8 9

[math-fun] ridiculously simple derivation (whose?) of Pythagorean triples
by Bill Gosper 29 Apr '13

29 Apr '13

In[570]:= (1+2*I)/(2+1*I) Out[570]= 4/5+(3 I)/5 In[571]:= (1+3*I)/(3+1*I) Out[571]= 3/5+(4 I)/5 In[572]:= (2+3*I)/(3+2*I) Out[572]= 12/13+(5 I)/13 In[573]:= (1+4*I)/(4+1*I) Out[573]= 8/17+(15 I)/17 In[586]:= Simplify/@ComplexExpand[(a+I*b)/(b+I*a)] Out[586]= (2 a b)/(a^2+b^2)-(I (a^2-b^2))/(a^2+b^2)

6 7

Re: [math-fun] Name for matrices whose rows & columns both sum to zero ?
by Henry Baker 29 Apr '13

29 Apr '13

About the only analogies I can think of are parity check codes, where the row/column sums are mod 2, or higher-order codes where the sums are in GF(2^k). But my original posting was about standard arithmetic over Q, R, C, etc. At 07:39 PM 4/28/2013, Victor Miller wrote: >I was thinking that too, but the elements of a doubly stochastic matrix are >non-negative (since they correspond to probabilities). > >Victor > >On Sun, Apr 28, 2013 at 10:33 PM, Michael Kleber ><michael.kleber(a)gmail.com>wrote: > >> In the square case, you can add 1/n to each entry and make each row and >> column sums to 1, a "doubly-stochastic matrix", about which much has been >> written. (The dimension of the space is certainly (n-1)^2, for example.) >> But I don't know of a name for the sum-to-0 version. >> >> --Michael >> >> On Sun, Apr 28, 2013 at 10:04 PM, Fred lunnon <fred.lunnon(a)gmail.com> >> wrote: >> >> > Though it's not (quite) obvious that element [n, n] is not >> > over-determined ... WFL >> > >> > On 4/29/13, Henry Baker <hbaker1(a)pipeline.com> wrote: >> > > Woops! At least one of these equations is redundant, so perhaps the >> > > dimension is n^2-2n-1 = (n-1)^2. >> > > >> > > (This part is obvious: take a random (n-1)x(n-1) matrix & pad it with one >> > > additional row & column, which consists of -row sums and -column sums.) >> > > >> > > At 05:21 PM 4/28/2013, Henry Baker wrote: >> > >>Is there a name for matrices whose rows & columns both sum to zero ? >> > >> >> > >>What about _square_ matrices of this type ? >> > >> >> > >>Clearly, there are n^2 unknowns and 2n equations, so the nxn matrices have >> > >> dimension n^2-2n = n(n-2).

3 2

[math-fun] Name for matrices whose rows & columns both sum to zero ?
by Henry Baker 29 Apr '13

29 Apr '13

Is there a name for matrices whose rows & columns both sum to zero ? What about _square_ matrices of this type ? Clearly, there are n^2 unknowns and 2n equations, so the nxn matrices have dimension n^2-2n = n(n-2).

4 4

[math-fun] nonHurwitz c.f.s--an inconvenient observation
by Bill Gosper 27 Apr '13

27 Apr '13

We're trying to find a number, like e^3, or probably easier, e^4 (from coth 2), that we can prove nonHurwitz. We are tantalized by the apparent breakdown of finite state when we subject the c.f. for coth 2 (with fractional terms 1/2,3/2,5/2,...) to a homographic function, vs the simple, repetitive behavior when we process coth 1/n (with terms n,3n,5n,...). In the latter case, finite state can be proven by simple matrix identities. E.g., the process of simply doubling (={{2,0},{0,1}}, representing (2#+0)/(0#+1)) coth 1 = 1,3,5,... produces exactly five outputs for every three inputs via the identity 2 0 1 + 6 k 1 3 + 6 k 1 ( ).( ) . ( ) . 0 1 1 0 1 0 5 + 6 k 1 2 + 12 k 1 1 + 3 k 1 ( ) = ( ) . ( ) . 1 0 1 0 1 0 1 1 1 1 2 + 3 k 1 2 0 ( ).( ).( ) . ( ) 1 0 1 0 1 0 0 1 I.e., input 6k+1,6k+3,6k+5 and output 12k+2,3k+1,1,1,3k+2 restoring the {{2,0},{0,1}} state, so twice 1,3,5,7,..., = 2,1,1,1,2,14,4,1,1,5,26,7,1,1,8,... . Left and right multiplying the equation by {{1,0},{0,2}} (= halving) produces the matrix proof of the reverse process: Five inputs produce three outputs, where we cancel the 2s in {{2,0},{0,2}} to get the identity matrix, which we erase. Every homographic function of a Hurwitz c.f. will produce one of these matrix equations. Here is the actual computation of 2 coth 1. In[356]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st,{{{2*#+1,1},{1,0}}&,0,{{2,0},{0,1}}},32]]] st takes a state vector containing the function for the nth input matrix, the current value of n, the (2x2) state matrix (initially, the function we wish to apply to the c.f.), and the output c.f. so far. For each output, it also Sows the current n. After 32 (input or output) steps, we have the current state vector and a list of how many inputs preceded each output: Out[356]= {{{2 #1+1,1},{1,0}}&,12,{{2,0},{0,1}}, 2,1,1,1,2,14,4,1,1,5,26,7,1,1,8,38,10,1,1,11} {1,0,0,0,2,1,0,0,0,2,1,0,0,0,2,1,0,0,0} We see that the state matrix has returned to {{2,1},{1,0}}, and the I/O behavior is repetitive: read one, output four, read two, output 1. The actual update function is Clear[st]; st[{f_, n_, M_?MatrixQ, cf___}] := Block[{xy = Divide @@ (M.{{1, 1}, {1, 0}}), t}, If[Floor@xy[[1]] == (t = Floor@xy[[2]]), Join[{f, Sow[n]}, {{{0, 1}, {1, -t}}.M, Sequence @@ {cf, t}}], xy = M.f[n]; {f, n + 1, xy/GCD @@ Join @@ xy, cf}]] Now let's allow fractional terms. To keep the state matrix canonical, we can scale the input matrices to be integers, e.g. {{1/2,1},{1,0}} -> {{1,2},{2,0}}. This will scale the state matrix determinant by -4 instead if -1, clearly blowing finite-state, but for the possibility of later scaling out common factors from the state matrix. The only change to the stepper is to replace Divide @@ (M.{{1, 1}, {1, 0}}) by Divide @@M, reflecting that we can no longer rely on the unread tail of the c.f. to exceed 1. This will typically introduce a one term latency which will mildly conceal state repetition. Let's compute 2 coth 1 as the identity function of 1*2,3/2,5*2,7/2,... instead of doubling 1,3,5,... as before. In[366]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st2,{{{2^(-1)^#*(2*#+1),1},{1,0}}&,0,{{1,0},{0,1}}},35]]] Out[366]= {{{2^(-1)^#1 (2 #1+1),1},{1,0}}&,14,{{27,2},{2,0}}, 2,1,1,1,2,14,4,1,1,5,26,7,1,1,8,38,10,1,1,11,50} {1,1,0,0,1,1,1,0,0,1,1,1,0,0,1,1,1,0,0,1} It's still finite state (modulo a term of latency, and a temporary determinant of -4). But now let's try something ridiculously simple: In[372]:= FromContinuedFraction[{{1/2}}] Out[372]= 1/4 (1+Sqrt[17]) In[373]:= ContinuedFraction[%] Out[373]= {1,{3,1,1}} I.e., let's extract the strictly periodic 1,3,1,1,3,1,1,... (why didn't it say {{1,3,1}}?) from 1/2,1/2,1/2,... . (And why won't it allow FromContinuedFraction[{{x}}]? Or {{1,1,0}}?) Anyway, here's the bad news: In[376]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st2,{{{1/2,1},{1,0}}&,0,{{1,0},{0,1}}},69]]] Out[376]= {{{1/2,1},{1,0}}&,52, {{6370761842645543,5705560984788822}, {5040360126932101,1330401715713442}}, 1,3,1,1,3,1,1,3,1,1,3,1,1,3,1,1,3} {4,5,0,4,3,0,6,3,0,4,5,0,4,5,0,4} It's not finite state! (Note the huge matrix.) The input and output are repetitive, but their timings are not. Instead we have a very interesting quinary pattern, which becomes ternary under the mapping {4,5,0}->a, {4,3,0}->b, {6,3,0}->c: In[377]:= TableForm[Partition[Partition[Differences[#[[2,1]]]&@ Reap[Nest[st2,{{{1/2,1},{1,0}}&,0,{{1,0},{0,1}}},1093]],3] /.{{4,5,0}->a,{4,3,0}->b,{6,3,0}->c},15]] Out[377]//TableForm= a b c a a b c a b c c a b c a a b c a a b c a b c c a b c a a b c a b c c a b c c a b c a a b c a b c c a b c c a b c a a b c a b c c a b c a a b c a a b c a b c c a b c a a b c a This means that obvious misbehavior of the matrix processing coth 2 does not guarantee misbehavior of its c.f., = (e^4+1)/(e^4-1). Yet this is anything but random. Is it fractal, or does it draw one under some interpretation? A less degenerate example is computing coth 1 from (2#+1)/(0#+1), where #:=0 + ContinuedFractionK[k, k, {k,∞}]=1/(e-1) : In[378]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st,{{{#,#+1},{1,0}}&,0,{{2,1},{0,1}}},69]]] Out[378]= {{{#1,#1+1},{1,0}}&,49, {{2206943012448662116158774811288656,2206950077348678728346652963751377}, {26920936494950091431033190362544,26369778840455766330813469539023}}, 2,6,10,14,18,22,26,30,34,38,42,46,50,54,58,62,66,70,74,78} {3,3,2,2,3,2,2,3,2,2,3,2,2,3,1,3,3,1,3} The output intervals are crazy, yet the terms are not. What is it about processing 1/2,3/2,5/2,... that assures crazy sizes, not just crazy intervals?: In[387]:= Column[{#[[1]],Differences[#[[2,1]]]}&@ Reap[Nest[st,{{{#+1/2,1},{1,0}}&,0,{{1,0},{0,1}}},666]]] Out[387]= {{{#1+1/2,1},{1,0}}&,155, {{326309420948894846183209753068665518244757108833, -1309845084617830597650227042950849295187806558}, {183300788310157256605231207606976793305330479468, 5656683762988769057687299987446265732036054360}}, 1,26,1,3,1,42,2,3,1,28,5,1,4,3,1,6,12,1,40,1,9,1,8,2,1,1,2,1,3,5,4,1,1,5,1,5, 8,1,2,1,1,2,16,1,3,2,6,4,4,14,3,2,1,2,3,1,2,1,18,4,1,1,1,32,1,4,2,6,6,4,2,1, 1,3,2,1,4,1,1,8,1,2,1,9,8,1,2,4,1,19,1,3,3,2,11,1,62,2,2,2,6,21,3,7,1,1,7,23, 1,19,1,4,1,1,1,1,5,2,13,2,7,25,6,2,3,36,3,1,9,2,379,2,5,1,1,3,1,1,1,36,26,1,22, 1,1,5,1,1,2,1,1,13,2,1,3,4,1,2,7,1,2,1,1,330,1,1,4,3,5,10,1,31,2,27,3,1,1,2,56, 3,3,4,153,1,1,1,1,2,2,1,1,1,18,2,4,3,1,10,1,8,3,20,2,14,4,1,50,5,1,2,1,16,3,3, 28,1,1,3,1,1,7,2,2,8,2,7,1,1,1,3,9,4,1,1,2,1,1,3,3,2,1,3,197,63,1,6,14,5,6,1,1,1, 2,6,11,3,7,7,2,3,13,1,1,1,4,1,1,2,2,1,1,2,2,14,1,4,3,1,17,4,1,2,1,11,1,5,1,11,2,2, 1,2,1,1,2,1,3,3,2,2,2,1,1,9,2,1,2,1,2,1,1,6,4,1,16,2,2,1,3,1,14,1,1,2,3,1,1,2,5,1, 104,3,6,1,1,1,10,2,39,1,2,1,8,4,2,1,13,1,2,17,575,1,1,4,87,1,9,1,8,1,1,2,6,6,1,2, 1,1,6,1,1,16,12,1,1,5,4,1,76,2,3,8,1,128,2,2,4,1,2,1,2,4,1,3,3,2,2,1,3,2,1,1,2,2,31, 4,2,1,4,1,4,1,2,2,2,2,5,3,2,1,3,3,355,1,1,9,2,2,1,1,3,19,72,11,2,2,2,1,23,1,2,31,2, 7,1,1,2,5,1,2,35,1,1,1,7,1,10,1,3,3,4,5,21,1,1,1,2,2,1,7,1,1,19,4,1,8,2,2,1,2,34,1, 59,4,1,2,4,28,1,1,1,1,1,3,3,4,1,13,45,1,11,1,5,1,9,1,3,1,3,3,1} {2,0,2,0,1,0,1,0,1,1,0,1,1,0,1,0,0,2,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0, 0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0, 1,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,0,2,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0, 1,1,0,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,2,0,0,0,1,0,1,0,0,0, 1,1,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,1,0,0, 1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0, 0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0, 0,0,0,1,0,2,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0, 0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,2,0,0,0,0,1,0,0,0, 1,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0, 0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0} 2 is getting rare. Are there finitely many? Are the 0 bursts bounded? If not, could that make a proof? We'd triumph by showing unbounded 1 bursts in the *output* sequence. Or even unbounded bursts < any fixed constant. And we only need to prove nonHurwitz for *any* (a e^4 + b)/(c e^4 + d), a,b,c,d rational. (Desi insults notwithstanding.) --rwg (Apologies: In[378] is confusing because ConfinuedFractionK uses {{0,num},{1,den}} style matrices, but st uses {{den,num},{0,1}}.) On Sun, Oct 7, 2012 at 2:12 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > The quasiperiod for the continued fraction of e ~ 2.718 can be written as > the three > polynomials {1,2k,1}, "modulo rotation and translation", e.g. {2k-2,1,1}. > It can also > be "inflated" by a factor of 2 or 3 or ..., e.g > {1,4k,1,1,4k+2,1} or {1,6k,1,1,6k+2,1,1,6k+4,1} or ... . > > If I heard him right, Julian has proved that given the Hurwitz # x > :={P0(k),P1(k),...}, > there is an inflation factor Δ ≤ (ad-bc)^4 such that the quasiperiod of > y:=(ax+b)/(cx+d) can be written by inflating x by Δ and then replacing each > polynomial Pi with an even number of constant polynomials, followed by a > polynomial with the same degree as Pi. In particular, linear terms cannot > arise > from nonlinear terms. The resulting CF of y may often be "deflated" to > have > a shorter quasiperiod than x. > --rwg > One use of this theorem is to detect the possibility or impossibility of > finding a > homographic transformation shortening a long quasiperiod. > > For some reason, Julian disavows calling this a "structure theorem". It > can > probably be extended to cover exponential (e.g.) as well as polynomial > terms. >

1 0

Re: [math-fun] Tan[Sin[x]]-Sin[Tan[x]] puzzles
by Bill Gosper 27 Apr '13

27 Apr '13

Here <http://gosper.org/flattop.png>'s a more traditional plot near z=0. --rwg

3 8

Re: [math-fun] "critical exponents" for columns resisting buckling
by Steve Witham 27 Apr '13

27 Apr '13

>Date: Fri, 26 Apr 2013 13:17:04 -0400 >From: Warren D Smith <warren.wds(a)gmail.com> >This way of doing things focuses attention on the "critical exponents" >which in 3D and 2D (we have shown nonrigorously) are <=2 and <=1.585 >respectively; >improvements versus Euler/Clausen/Keller's 7/3=2.3333 and 2 respectively. >Can these exponents be shrunk by using better fractals? >Can they be justified rigorously? I don't know but Bucky Fuller's notion of "tensegrity" is structures built out of members that are only being used purely for tension or purely for compression, on the theory that otherwise, the material isn't being used efficiently. He described tensegrity "masts" which are columns built in this way. The basic design looks like tetrahedra in stacked cubical cells... with none of the compression members touching. In some of the designs the struts have balls at their ends. Of course, solid or even tubular compression struts have the same inefficiency, so... "The concept that tensegrity is fractal, at different orders of magnitude, was often discussed by Fuller in his lectures." http://tensegrity.wikispaces.com/Mast Nice examples given there: the interior structure of bone, and the way the spine is held straight by muscle tension between projections from the vertebrae. This piece http://www.unisa.it/uploads/4760/course.pdf has some math about minimizing weight for a given strength and number of parts. Those two urls were the first two google hits for "fractal tensegrity column"; googling "tensegrity mast" gives pics and videos near the top. --Steve

1 0