November 2011 - mathfun@mailman.xmission.com

Re: [math-fun] A Nice Sequence
by Warren Smith 20 Nov '11

20 Nov '11

>"number of distinct values taken by i^i^...^i (with n i's and parentheses inserted in all possible ways)" where i = sqrt(-1) and ^ denotes the principal value of the power function [A198683] --If i were replaced by some generic number, then all the parenthesizations would yield distinct values and the count would be a known Catalan number (which is an upper bound on this i-based count, therefore). Right? WRONG!!! Because (x^x)^(x^x) = (x^(x^x))^x FOR *ANY* x !!! so you can actually get a stronger "generic" upper bound than the Catalan numbers! So the more interesting question seems to be: what is this (generic x) count? However, certain special numbers lower the count. In particular using 1 or -1 as x, there always is only one distinct value. So Reduced-Catalan is the maximum, and 1 is the minimum, count. I'm not sure what is so special about i from this point of view. A more systematic question would be to ask what real (or complex) values replacing "i" yield the minimum counts, in order of increasing count. I note (2^2)^2 = 4^2 = 16 and 2^(2^2) = 2^4 = 16 g^((g^g)^g) = (g^g)^(g^g) = (g^(g^g))^g where g= (1+sqrt(5))/2 = golden ratio = 1.618033988 [also 1/g works instead of g] L^(L^(L^L)) = ((L^L)^L)^L where L = ln(3)/LambertW(ln(3)) = 1.825455023 Q^(Q^(Q^Q)) = (Q^Q)^(Q^Q) = (Q^(Q^Q))^Q where Q=1.776775040 r^((r^r)^r) = ((r^r)^r)^r where r=sqrt(3)=1.732050808 [also -sqrt(3)] -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] exact rational dragon
by Bill Gosper 20 Nov '11

20 Nov '11

In[135]:= $RecursionLimit = 9999; Clear[Drag]; Drag[t_, a1_: 1, a0_: 0] := Drag[t, b1_: 1, b0_: 0] = (Drag[t, s1_: 1, s0_: 0] = ((a0 - s0)/(s1 - a1)); Module[{t2 = 2*t, n}, n = Floor[t2]; t2 -= n; Switch[n, 0, (I + 1)/2*Drag[t2, a1*(I + 1)/2, a0], 1, 1 + (I - 1)/2*Drag[1 - t2, (I - 1)/2*a1, a1 + a0], 2, 1]]) E.g., In[136]:= Drag[7/22] Out[136]= 23/82 + 39 I/82 In[137]:= % - Drag[113/355] Out[137]= 517517964757026532787/96808512898827726880686 + 650828352727980554837 I/96808512898827726880686 In[138]:= N[%] Out[138]= 0.00534579 + 0.00672284 I (The Dragon function is continuous.) Dividing the domain [0,1] into equal fifths, ListLinePlot[ Partition[Table[{Re@#, Im@#} &@Drag[t/4/2048], {t, 8190}],1638], AspectRatio -> Automatic, Axes -> None] may surprise you: http://gosper.org/dragon5ths.png The obligatory continuous texture drift: ListLinePlot[Table[{Re@#, Im@#} &@Drag[t], {t, 0, 1, 1/513}], AspectRatio -> Automatic, Axes -> None] and ListLinePlot[Table[{Re@#, Im@#} &@Drag[t], {t, 1/1024, 1, 1/513}], AspectRatio -> Automatic, Axes -> None] http://gosper.org/driftdrags.png --rwg

2 1

[math-fun] dragon triple points
by Bill Gosper 20 Nov '11

20 Nov '11

Arguing from self similarity, Julian found In[240]:= Drag /@ {13/30, 21/30, 23/30} Out[240]= {1/2 + I/6, 1/2 + I/6, 1/2 + I/6} i.e., the function visits 1/2+i/6 three times, where Drag is the exact rational definition I sent recently. By dragon/2 ~ dragon, In[90]:= Drag /@ ({13/30, 21/30, 23/30}/2) Out[90]= {1/6 + I/3, 1/6 + I/3, 1/6 + I/3} and In[91]:= Drag /@ (1 - {13/30, 21/30, 23/30}/2) Out[91]= {2/3 + I/6, 2/3 + I/6, 2/3 + I/6} In[92]:= Drag /@ ((1 - {13/30, 21/30, 23/30}/2)/2) Out[92]= {1/4 + (5 I)/12, 1/4 + (5 I)/12, 1/4 + (5 I)/12} By iterating #/2 and 1-#/2, we can construct a dense set. After one iteration, all three inverse images will be on the same side of 1/2, but Julian points out there are other cases with denominator 30*2^n, e.g., In[99]:= Drag /@ {199/480, 71/160, 329/480} Out[99]= {11/24 + (7 I)/24, 11/24 + (7 I)/24, 11/24 + (7 I)/24} There appear to be no quadruple points. We found a slightly questionable proof that all spacefilling functions are dense with triple points. (Lemma: They map closed intervals onto closed sets.) By methodical search, Julian found another family of denominators: In[93]:= Drag /@ {13/28, 17/28, 19/28} Out[93]= {3/5 + (3 I)/10, 3/5 + (3 I)/10, 3/5 + (3 I)/10} In[94]:= Drag /@ ({13/28, 17/28, 19/28}/2) Out[94]= {3/20 + (9 I)/20, 3/20 + (9 I)/20, 3/20 + (9 I)/20} We did not find any families of denominators besides 28*2^n and 30*2^n. --rwg PS, while investigating the (three valued) inverse dragon function, Neil made the lovely monochrome image: http://gosper.org/draglarge.png

1 0

[math-fun] Fast Divisionless Determinant and Characteristic Polynomial of Matrix
by Warren Smith 20 Nov '11

20 Nov '11

Fast Divisionless Determinant and Characteristic Polynomial of Matrix Warren D. Smith, Nov. 2011 By "characteristic polynomial" of a matrix M we shall mean charpoly(M,x) = det(I*(1-x)+M*x) = det(I-[I-M]*x) which is not exactly the same as the usual definition but the two are easily interconverted. When x=1 this is det(M) and when x=0 it is det(I)=1. Consider the 2nX2n block matrix (with nXn blocks) M = [E F] [G H] One form of the Schur identity is det(M) = det(E H - E G inverse(E) F) which leads to one way to evaluate det(M) in a number of steps of the same order as an nXn matrix multiplication and nXn matrix inversion. [And it is impossible to evalate det(M) is smaller order #steps, as can be shown using fact the gradient of det is the adjoint so we could use det plus algorithmic differentiation to compute matrix inverse fast.] If M happens to be the identity matrix this recursive process generates smaller identity matrices at every step on the way. Here however we shall be interested in no-division algorithms. Let D=I-E. charpoly(M,x) = charpoly(E,x) * det( [I-H]*x - G inverse(I-D*x) F*x*x) = charpoly(E,x) * det( [I-H]*x - G [I+xD+x^2D^2+x^3D^3+...] F *x*x) where in the infinite series it suffices to stop after terms in x^n are reached (or stop anyplace further on), because this is a formal Maclaurin series which we know must be a polynomial in x of degree n so we know higher powers of x are all going to come out with coefficient=0 in the end so we do not need to calculate them. Now use the product (1+y+y^2+y^3+...+y^127) = (1+y^64)(1+y^32)(1+y^16)(1+y^8)(1+y^4)(1+y^2)(1+y) to evaluate the series fast (and use repeated squaring of course). We then have charpoly(M,x) = charpoly(E,x) * det(H - G [I+xD][I+x^2D^2][I+x^4D^4]...[I+x^pD^p] F *x*x) where P is any power of 2 with P>=n/2. This halves the size of the matrix and after log(n) recursive levels we bottom out at 1x1 matrices. When x-->0 this recursive process generates identity matrices every step of the way. Then for general x we get Maclaurin series whose constant terms are identity matrices every step of the way, which enables us the compute the needed matrix inverse using the 1/(I-K*x) Maclaurin expansion as a product trick as above, each step of the way. To multiply two nXn matrices with scalar entries takes MatMult(n)=O(n^2.376) steps. [Don Coppersmith & Shmuel Winograd: Matrix multiplication via arithmetic progressions J. Symbolic Computation 9,3 (1990) 251-280.] To multiply two nXn matrices with kth-degree polynomial(x) entries takes MatMult(n)*k+O(k*logk*n^2) steps, which is O(k*n^2.376) steps if logk<n^0.376, by using FFT-based fast convolution to multiply polynomials with O(k) coefficient-multiplications. The product has log(n) terms and is multiplied in tree-fashion. The whole recursive scheme's runtime basically obeys T(2*n) = 2*T(n) + MatMult(n)*n*logn hence T(n) = O(Matmult(n)*n*log(n)) = O(n^3.38). THEOREM (DIVISIONLESS DET & CHARPOLY) What we have called the "characteristic polynomial" of an matrix M, can be computed (i.e. all its coefficients computed) in O(n^3.38) arithmetic operations if M is nXn, by a scheme which never divides two matrix entries; it only uses +, -, and * and employs O(log(n)) weird scalar constants inside the FFT. [Then the determinant of M is just this polynomial evaluated at x=1.] This runtime is a factor O(n) slower than the number of steps required for det(M) if division is allowed. Also note, our divisionless algorithm is massively parallelizable. Also note, we can by storing the "computation tree" as we proceed, then afterwards "backing down the tree" from the root (det) to the leaves( matrix entries) using the chain rule compute the partial derivatives of the det with respect to all the matrix entries, i.e. compute the matrix Adjoint (or whatever it is called, "Adjugate" maybe) also in this same time bound and also without use of any division, but need a lot of memory. ( See "reverse" method in http://en.wikipedia.org/wiki/Automatic_differentiation ) It also is possible to achieve O(n^3)-step determinant evaluation using only ONE division by triangularizing the matrix using row linear combinations, keeping track of the multiplication factor as you go. Det(triangular matrix) is then trivial (product of diagonal entries) and then at the end perform the one division, by the product of multiplication factors. (But this method is a lot less massively parallelizable.) Indeed, you can achieve O(MatMult(n)) steps by using rational numbers to represent intermediate results in a fast det algorithm then do the one division in the final rational number. It seems a bit odd that reducing from one to zero divisions costs you this much extra work. Or perhaps it doesn't. If you're smarter.

1 0

[math-fun] A Nice Sequence
by Hans Havermann 20 Nov '11

20 Nov '11

Alonso Del Arte notes on SeqFan that this "nice" count (authored recently by Vladimir Reshetnikov) of the "number of distinct values taken by i^i^...^i (with n i's and parentheses inserted in all possible ways*) where i = sqrt(-1) and ^ denotes the principal value of the power function" [A198683: 1, 1, 2, 3, 7, 15, 34, 77, 187, 462, 1152, 2926, ...] breaks down calculating the next (thirteenth) term, using the Mathematica formulation f[1] = {I}; f[n_] := f[n] = Union[Flatten[Table[Outer[Power, f[k], f[n-k]], {k, n-1}]], SameTest - > Equal]; Table[Length[f[n]], {n, 13}], with overflow errors. I'm wondering if anyone here is able to determine subsequent terms. *Example: a(4) = 3: there are 5 possible parenthesizations but they give only 3 distinct values: i^(i^(i^i)), i^((i^i)^i) = ((i^i)^i)^i, (i^i)^(i^i) = (i^(i^i))^i.

1 0

[math-fun] Volume=Integer/3 for Heronian tetrahedra?
by Warren Smith 19 Nov '11

19 Nov '11

>Michael Reid: What is the situation in 3 dimensions? Can a tetrahedron with integer edge lengths have a volume that is one twelfth (one sixth, one fourth, ... ) of an integer, without being an integer itself? WDS: My computer did the following. There are 6 edges of a tetrahedron. It tried all 4^6=2^12=4096 possibilities for the edge lengths (mod 4). A possibility was "unacceptable" if it led to 16*(some triangle area)^2 = nonsquare (mod 1024) or 2*288*(tetrahedron volume)^2 = nonsquare (mod 1024) or GCD(all 6 edge lengths, 4) != 1. Among the acceptable possibilities, it found that 2*288*(tetrahedron volume)^2 was always 0 or 448 (mod 576). If it were always 0 (and if no bugs in my program...) then we would have proven "Any tetrahedron with integer edge lengths and rational face areas and rational volume, automatically has integer volume." But the possibility of 448 means that integer/3 volumes have not been ruled out. I also tried mod-3 analysis instead of mod-4, but that reached the same conclusion: 0 and 448 only. It seems to me possible that such a modular analysis might be able to show nonexistence of Heronian 5-simplices. If that can be done it would solve RK Guy's open problem D22. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2

Re: [math-fun] quarter-Heroic triangles are Heronian
by Michael Reid 19 Nov '11

19 Nov '11

> THEOREM: The "Heronian" triangles can also be characterized as the > triangles with integer sides and rational area (they then automatically have > integer area). > > CORRECTED PROOF: It is much easier than that. Since 16 (area)^2 = 4(a^2 b^2 + b^2 c^2 + c^2 a^2) - (a^2 + b^2 + c^2)^2 , it follows that if a + b + c is odd, then 16 (area)^2 = 3 mod 4 , which is not a square. What is the situation in 3 dimensions? Can a tetrahedron with integer edge lengths have a volume that is one twelfth (one sixth, one fourth, ... ) of an integer, without being an integer itself? > I googled Heronian triangles and a lot of what we've been saying was > already known!! > Duh!! > > Paul Yiu: > Heronian triangles are lattice triangles, > Amer Math Monthly 108,3 (March 2001) 261-263 > http://math.fau.edu/Yiu/AMM2001Heron.pdf > Proves "Reid's" theorem. Indeed more strongly shows > if the sides are sqrt(integer) and the area is rational, > then embeddable on integer lattice. The stronger result needs an additional hypothesis. Otherwise take a Heronian triangle and scale by a factor of sqrt(3) ; the resulting triangle cannot be embedded with integer coordinates. Indeed, he mentions the condition GCD(x, y, z) = 1 , where x , y and z are the squares of the edge lengths. But he curiously omits it from his definition of "geodetic" at the end. Michael Reid

2 1

[math-fun] Heronian triangles (google knows more than us)
by Warren Smith 19 Nov '11

19 Nov '11

I googled Heronian triangles and a lot of what we've been saying was already known!! Duh!! Paul Yiu: Heronian triangles are lattice triangles, Amer Math Monthly 108,3 (March 2001) 261-263 http://math.fau.edu/Yiu/AMM2001Heron.pdf Proves "Reid's" theorem. Indeed more strongly shows if the sides are sqrt(integer) and the area is rational, then embeddable on integer lattice. (But I think Reid's proof also shows this.) I think Yiu's proof is not as nice as Reid's and my stuff because he does not use the Gaussian Integers. http://www.maa.org/mathdl/CMJ/methodoflastresort.pdf This 1998 paper reports how Brahmagupta found around 625AD that the consecutive-integer-sides Heronian triangles arise from Pell equation. The same result was rediscovered by Prof. Bill Richardson in 2010: http://www.math.wichita.edu/~richardson/heronian/heronian.html http://sci-gems.math.bas.bg:8080/jspui/bitstream/10525/382/1/sjc058-vol2-nu… http://www.wm.uni-bayreuth.de/fileadmin/Sascha/Publikationen/On_Heronian_Tr… Describe several algorithms for the generation of integer Heronian triangles with diameter at most n. Two of them have running time O(n^(2+epsilon)), which beats cubic time. http://forumgeom.fau.edu/FG2007volume7/FG200718.pdf Heronian Triangles Whose Areas Are Integer Multiples of Their Perimeters Paul Yiu: Construction of indecomposable Heronian triangles, Rocky Mountain Journal of Mathematics 28 (1998) 1189-1202. http://math.fau.edu/yiu/Southern080216.pdf Heronian Triangles Wm. Fitch Cheney, Jr. The American Mathematical Monthly Vol. 36, No. 1 (Jan., 1929), pp. 22-28

2 1

[math-fun] quarter-Heroic triangles are Heronian
by Warren Smith 19 Nov '11

19 Nov '11

THEOREM: The "Heronian" triangles can also be characterized as the triangles with integer sides and rational area (they then automatically have integer area). CORRECTED PROOF: For a primitive triangle, with sides a,b,c integer with GCD(a,b,c)=1, (a,b,c)=(even,even,even) is impossible (not primitive). Consider a,b,c mod 4. The squares mod 4 are 0 and 1. The only ways 16*area^2=p*(p-2a)*(p-2b)*(p-2c) where p=a+b+c can be a square, as we find by exhaustive consideration of all 4*4*4=64 possibilities [then exclude cases with all of {a,b,c} even], are these six: (a,b,c) mod 4 = (0,1,1) (0,1,3) (0,3,3) (1,1,2) (1,2,3) (2,3,3) [or some re-order of those]. in which cases 16*area^2 is found to be 0 mod 64 in every case. Hence area is an integer (not a quarter integer). QED. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Heronian tetrahedra (google search)
by Warren Smith 19 Nov '11

19 Nov '11

RK Guy, Unsolved Problems In Number Theory, problem D22: Simplexes with rational content. "Are there simplexes in any number of dimensions, all of whose contents (lengths, areas, volumes, hypervolumes) are rational?" Ralph Heiner Buchholz: Perfect pyramids, Bulletin of the Australian Mathematical Society 45,3 (1992) 353-368 proves an infinite number of Heronian tetrahedra exist. Randall L. Rathbun [randall AT ncr-sd.UUCP] in 1987 made a huge database of Heronian triangles. He wanted to find one with rational medians. He failed, but claims with Buchholz to have a proof using Somos(5) sequences (!!) that an infinite number of Heronian triangles with two rational medians exist. He gives as examples Sides Medians Area 73 51 26 sqrt(3796) 48.5 17.5 420 875 626 291 sqrt(557580.25) 572 216.5 55440 A proof appeared here showing how every rational point on a certain elliptic curve corresponded to such a triangle: Ralph H. Buchholz & Randall L. Rathbun: Heron Triangles And Elliptic Curves, Bull. Australian Math. Soc 58 (1998) 411-421 They conjecture there are no Heronian triangles with all 3 medians rational.

1 0