June 2012 - mathfun@mailman.xmission.com

[math-fun] why can a line of slope 10^n determine n decimal digits of π?
by Gary Antonick 19 Jun '14

19 Jun '14

Just noticed this yesterday and can't figure out why it works. Draw a circle with radius 1 around 0,0. Draw a line with slope -10 that hits the circle at 1,0. This line will also hit the circle again and make a little arc. The length of the arc will be about 1/31 the perimeter of the circle. Now try again with a line of slope -100. The line will create an arc 1/314 of the circle. Starting to look a bit like pi. Am wondering why this is. In case I made a mistake here's what I'm trying to describe.. if the circle were a clock the first line would cut an arc from 15 minutes (3:00) to almost the 13 minute mark.

4 7

[math-fun] sqrt(pi)
by Bill Gosper 24 Mar '13

24 Mar '13

Pairwise combining the terms of A&S 6.5.31 (upper Gamma CF), then adding last week's lower gamma CF: In[185]:= Equal[Gamma[ z], ((y^z*((1/(cfk[n*(z - n), -z + y + 2*n + 1, List[n, Infinity]] - z + y + 1)) + (1/(z + cfk[n*y, z - y + n, List[n, Infinity]] - y))))/(E^y))] z 1 Gamma[z] == (y (------------------------------------------- + -y + z + cfk[n y, n - y + z, {n, Infinity}] 1 y -----------------------------------------------------------)) / E 1 + y - z + cfk[n (-n + z), 1 + 2 n + y - z, {n, Infinity}] where cfk:=ContinuedFractionK and y>0 can be chosen to optimize convergence. Specializing, In[186]:= % /. z -> 1/2 /. y -> 1 Out[186]= 1 Sqrt[Pi] == (-------------------------------------- + 1 1 -(-) + cfk[n, -(-) + n, {n, Infinity}] 2 2 1 ------------------------------------------) / E 3 1 3 - + cfk[(- - n) n, - + 2 n, {n, Infinity}] 2 2 2 In[192]:= N[List @@ %186 /. cfk[num_, den_, _] :> ContinuedFractionK[num, den, {n, 9}]] Out[192]= {1.77245, 1.77244} This is the first non-asymptotic sum or CF I've seen for sqrt(pi). But the sum behind the lowergamma cf has been there all along, so I must not have been paying attention. --rwg

2 3

[math-fun] Nice measure for Life patterns?
by Mike Stay 04 Jul '12

04 Jul '12

I'd like to compute the first bits of the "halting probability" of Conway's life; since CAs don't halt, I'd like to compute the probability that it evolves to a state that's easily detectable by Golly, like all empty or a still life or cyclic. (Also, I know the number is uncomputable, but that doesn't preclude a finite computable prefix.) Since any translation or reflection of a pattern has the same outcome as the original, I'd like to choose a measure on the set of cells such that computing the measure of all the translations and reflections of a pattern is easy. Any suggestions? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

5 8

Re: [math-fun] Vector puzzle
by Dan Asimov 02 Jul '12

02 Jul '12

Christof wrote: << So we have n x 2^n numbers and the child sets any *arbitrary* (not necessarily small) subset of those to zero, correct? regarding the puzzle: << For some integer n > 0 you have all 2^n vectors of dimension n whose entries are +1 or -1. Of course the sum of all 2^n of these vectors is the 0 vector. Then your three-year-old child changes some of the entries of some of these vectors to 0. Show that there is still a nonempty subset of the new set of 2^n vectors that sums to the 0 vector. >> Yes, exactly. Any subset of the n(2^n) components of the original 2^n vectors may be changed to 0's. The problem is to show there is always some nonempty subset of the resulting set of 2^n vectors that sums to the 0 vector. --Dan ________________________________________________________________________________________ It goes without saying that .

3 4

[math-fun] optimum logic circuit to compute "count>=2" binary threshold function (and LIFE)
by Warren Smith 02 Jul '12

02 Jul '12

Consider the threshold=k binary function on N bits. That is, it is 1 if at least k of the N input bits are 1, otherwise it is 0. How many logic gates do you need to compute these functions? ======k=1======== Obviously, when k=1, just a big logical-OR does the job, i.e. only 1 gate with N inputs, or if you insist on 2-input gates only, then a tree with N-1 OR gates will do, and with depth<=lg(N) where lg(x)=log2(x). ======k=2======== When k=2, I discovered an optimal solution yesterday. Let G(N) be the number of 2-input gates needed. When N=2: output=AND(a,b) hence G(2)=1. G(3)<=5 since majority(x,y)=x*y + y*z + z*x which works regardless of whether the symbol + is interpreted as inclusive or exclusive OR. (*=AND.) If this is rewritten majority(x,y)=(x+z)*y + x*z then G(3)<=4. When N=4: compute z=OR(AND(a,b), AND(c,d)), y=AND(OR(a,b), OR(c,d)), output=OR(y,z). This shows G(4)<=7. When N=even: compute z=OR(thresh2(left N/2 bits), thresh2(right N/2 bits), y=AND(ORtree(left N/2 bits), ORtree(right N/2 bits), output=OR(y,z) which shows G(N)<=2*G(N/2)+N-2+1+1+1=2*G(N/2)+N+1 hence G(8)<=23 G(16)<=63 etc, G(N)<=N*lg(N)-1 is the general formula. But meanwhile, googling found this paper Ilan Newman & Avi Wigderson: Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy, SIAM J. Discrete Mathematics 8,4 (1996) 78-87 http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/HNW96/entropy.pdf and the theorem they mention on page 7 which they re-prove but also say was previously proven by Marc Snir: The covering problem of complete uniform hypergraphs, a note, Discrete Maths. 27 (1979) 103-105 shows (by taking k=2 and also using the fact a binary tree with L leaves must have L-1 internal nodes including the root) G(N)>=N*lg(N)-1. Hence G(2)>=1 G(3)>=4 G(4)>=7 G(8)>=23 G(16)>=63 etc which shows my threshold=2 circuit-constructions are exactly optimal when N=2, 4, 8, 16 and actually forever. It also shows these are optimal: G(3)=4 G(6)=15 G(12)=43 but we only have 110<=G(24)<=111. It would be surprising if this were not already known, but I did not see any mention of any circuit construction in Newman+Wigderson. =======k=3======== Moving on, what about threshold=3? By the way, if you need a use for this, since everyone on this group seems in love with the "game of LIFE" I point out that is defined entirely using binary threshold functions, so a fast "bitboard" implementation of LIFE would want to know about these circuits. Letting H(N) be the number of 2-input AND and OR gates needed, I can show H(3*N) <= 3*H(N) + 3*N + 3*G(N) + 12 and as a base case H(3) = 2 by using a 3-input AND gate. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

Re: [math-fun] Heron's formula/Cayley-Menger determinant
by Henry Baker 01 Jul '12

01 Jul '12

I found Fred's cool paper on arxiv. Perhaps some of my ideas can make a 2D version of the embedding theorem a little more elegant. BTW, my determinant III of complex numbers a,b,c: |0 a b c | |a 0 c' b'| |b c' 0 a'| |c b' a' 0 | when c=-a-b can be simplified with row & column operations to |a a' 0 c'| |b b' 0 0 | |0 0 a b | |0 0 a' b'| thus making obvious the factorization (ab'-a'b)^2. (We note again that ab'-a'b is pure imaginary, thus the square is negative real.) At 03:52 AM 6/30/2012, Fred lunnon wrote: >On 6/30/12, Henry Baker <hbaker1(a)pipeline.com> wrote: >> ... >> Is there a name for triangles whose sides are integers, and _which can >> also be embedded in the plane with integer coordinates for the vertices_ ?? >> ] > >"Heronian". > > If the vertices are rational, then the area is rational via the standard determinant >giving area in terms of Cartesian coordinates [which ought to have a name, though >I know of none]. If the sides are integers and the area rational, then the triangle is >Heronian by definition [and furthermore its area 6x integer]. > > Conversely, if a triangle is Heronian then it may be embedded with integer vertices >via Yiu's theorem --- see the remarkable complex GCD proof by Michael Reid which >was discussed in math-fun last year. > > An analogous argument applies in 3 dimensions. > >Fred Lunnon

2 1

Re: [math-fun] vector puzzle
by Bill Gosper 30 Jun '12

30 Jun '12

Evil child Julian says f(n)>n by preserving the all-ones vector, and in every other vector zeroing everything but one of the -1s. But in fact, f(n)=2^n ! Have the evil child zero everything before the last +1 in each vector (leaving (-1,…,-1) alone), and suppose that the nonempty subset S sums to 0. Since none of the modified vectors has a 0 in the last position, one of the modified vectors in S must have a -1 in the last position. Then its second-to-last position is nonzero, so there must be some (possibly the same) modified vector in S with a -1 in the second-to-last position. Continuing like this, there must be a modified vector in S with first entry -1, which could only be (-1,…,-1). In order for the sum to equal zero, there must be a modified vector in S with first entry +1. This must be (1,-1…,-1). This gives a sum of (0,-2,…,-2), so there have to be (at least) two modified vectors in S with second entry 1, and since there are only two such modified vectors (the original vectors must have had -1s in all but the first two positions and second entry +1), we must include them both. The sum of the vectors so far is (0,0,-4,…,-4). To get rid of that first -4, we need to include in S all four of the modified vectors which are equal to (0,0,1,-1,…,-1) (those that began life as (±1,±1,1,-1,…-1)), which gives us a running sum of (0,0,0,-8,…,-8). Continuing like this, we must include in S all eight (0,0,0,1,-1,…,-1)s, all sixteen of those with fifth entry +1, etc. Every modified vector must have a +1 in some position or be (-1,…,-1), so S contains all 2^n modified vectors. --Julian -------------------- >Dan Asimov:> Warren brings up the very interesting question:> For any such "0-modification" of the set {-1,1}^n> (i.e., so that some components of some vectors become 0,> the rest remaining unchanged), what is the smallest number> f(n) such that there is always a nonempty subset S of modified> vectors summing to the 0 vector, with #(S) <= f(n) ??? -- 1. In the Amit proof the initial vector which Asimov had taken as all 1's, could instead be taken to be anything... basically, we can change the signs of all the Jth entries of each vector, for any particular J, and do this repeatedly for different J, before we begin Amit's proof. So there are really 2^n different such proofs and we can ask which one yields the smallest 0-sum set. How much does that help? I do not know. If we believed that the map from v(j) to v(j+1) used in the Amit Alon proof acted like a random map on a 2^n-element state space, then we would expect a cycle of length 2^(n/2) roughly, hence subset size upper bounded by this. I see little reason to believe that, though. 2. Another thing is, in my old solution of a modified easier version of Asimov's vector puzzle -- where I asked merely that two distinct subsets exist whose sums were either equal or negations -- that proof method had the advantage that you could get bounds on the size of the two subsets. Specifically, the number of ways to choose a subset of cardinality <= S each is roughly 2^(n*S) / S! and the number of possible vector sums (identifying negations) is at most roughly (1/2) * (2*S+1)^n so if we ask for the threshold S at which the former first exceeds the latter, we get S=3 for large n. 3. That suggests the conjecture that f(n) remains bounded as n-->infinity. 4. However, we could instead conjecture that f(n) grows unboundedly; and hope to prove it by creating a good strategy for the evil child. We have f(1)=2 and earlier posts showed f(2)>=3 and f(3)>=5. _______________________________________________

2 1

Re: [math-fun] Heron's formula/Cayley-Menger determinant
by Henry Baker 30 Jun '12

30 Jun '12

Although my matrix III is symmetric, but not Hermitian, it is possible to convert it into the following matrix by simple row & column swaps: |a b' c' 0 | |b a' 0 c'| |c 0 a' b'| |0 c b a | If we're willing to give up integrality, we can always rotate the triangle so that the "a" side is parallel to the real axis, i.e., without loss of generality, we can make the "a" vector real. In this case, a=a', so the above matrix _is_ Hermitian. (I don't know of what use this is, however!) At 11:02 PM 6/29/2012, Pacher Christoph wrote: >Henry Baker wrote: > >> Matrix III is also a rare example of a _symmetric_ complex matrix >> that is _not Hermitian_. > >Isn't a symmetric matrix A Hermitian iff A is real symmetric ?! > >Christoph

1 0

Re: [math-fun] Heron's formula/Cayley-Menger determinant
by Henry Baker 30 Jun '12

30 Jun '12

Matrix III isn't real. a,b,c are the side _vectors_ as complex numbers. At 11:02 PM 6/29/2012, Pacher Christoph wrote: >Henry Baker wrote: > >> Matrix III is also a rare example of a _symmetric_ complex matrix >> that is _not Hermitian_. > >Isn't a symmetric matrix A Hermitian iff A is real symmetric ?! > >Christoph

2 2

Re: [math-fun] Heron's formula/Cayley-Menger determinant
by Henry Baker 30 Jun '12

30 Jun '12

[P.S.: Determinant III does actually _factor_ as (ab'-a'b)^2, once I set c=-a-b. Note that ab'-a'b is _pure imaginary_, so its square is a negative real number. I usually denote ab'-a'b as -2i(axb), where "axb" is my "cross product" of complex numbers. So Determinant III = (-2i(axb))^2=-4(axb)^2. We now have 2 different ways of factoring the same expression: -4(axb)^2 = -(-|c|+|b|+|a|)(|c|-|b|+|a|)(|c|+|b|-|a|)(|c|+|b|+|a|) This isn't a problem unless a,b are Gaussian integers and |a|,|b|,|c| are real integers; in this case, we have to be able to pair up the factors on the right hand side to make a square integer. Is there a name for triangles whose sides are integers, and _which can also be embedded in the plane with integer coordinates for the vertices_ ?? ] The Cayley-Menger determinant form for Heron's formula of the area of a triangle is well known: http://mathworld.wolfram.com/HeronsFormula.html -16 (Triangle Area)^2 = (Determinant "I") |0 a b c| |a 0 c b| |b c 0 a| = |c b a 0| (Determinant "II") |0 1 1 1| |1 0 cc bb| |1 cc 0 aa| = |1 bb aa 0| (c - b - a) (c - b + a) (c + b - a) (c + b + a) = (|c| - |b| - |a|) (|c| - |b| + |a|) (|c| + |b| - |a|) (|c| + |b| + |a|) where a,b,c are the (real) triangle side lengths, and aa=a*a=|a|^2, bb=b*b=|b|^2, cc=c*c=|c|^2. Determinant II is obtained from Determinant I by pre & post multiplication by real diagonal matrices, and vice versa. E.g., see Muir's Theory of Determinants, p.44. I know that determinantal identities are a dime a dozen, but here's one which I believe is new: This time, instead of using a,b,c for the (real) triangle side lengths, I use a,b,c for the _complex_ triangle side _vectors_, arranged head-to-tail so that a+b+c=0, and a',b',c' are the complex conjugates of a,b,c, respectively. Then, -16 (Triangle Area)^2 = (Determinant "III") |0 a b c | |a 0 c' b'| |b c' 0 a'| |c b' a' 0 | (Determinant "IV") |0 1 1 1 | |1 0 cc' bb'| |1 cc' 0 aa'| |1 bb' aa' 0 | Note that Determinant IV is _real_ and is _identical_ to Determinant II, because aa'=|a|^2, bb'=|b|^2, cc'=|c|^2. Determinants III and IV are interconvertible using pre & post multiplication by diagonal matrices with _complex_ entries. We also note that while Determinant IV = II = I can be factored, Determinant III cannot, because |a|=sqrt(aa'), |b|=sqrt(bb'), |c|=sqrt(cc') are not necessarily rational. Matrix III is also a rare example of a _symmetric_ complex matrix that is _not Hermitian_.

4 3