July 2012 - mathfun@mailman.xmission.com

[math-fun] three term recurrence ⇏ CF
by Bill Gosper 05 Jul '12

05 Jul '12

Given F[c_] := HypergeometricPFQ[{a, b, c}, {d, e + c}, 1], there are many ways to get the three term recurrence r[c] == -(((1 + c - d) (c + e) (1 + c + e))/((1 + c) (1 - a + c + e) (1 - b + c + e) (-(((1 + c + e) (1 + a (-1 + b - c) + 3 c - b (1 + c) + 2 e + (2 c - d) (c + e)))/ ((1 + c) (1 - a + c + e) (1 - b + c + e))) + r[1 + c]))) with r[c]:=F[c+1]/F[c]. (E.g. A&S or DLMF 15, or the 3x3 matrices in the "3F2 Rosetta stone" (after j->j+k), or Annihilator in HolonomicFunctions.m, or my CONTIGUATE function that uses the extra parameters feature of the indefinite summation algorithm.) Unfortunately, r[c] ≠ ContinuedFractionK[-(((1 - d + k) (e + k) (1 + e + k))/((1 + k) (1 - a + e + k) (1 - b + e + k))), -(((1 + e + k) (1 + 2 e + a (-1 + b - k) + 3 k - b (1 + k) + (e + k) (-d + 2 k)))/ ((1 + k) (1 - a + e + k) (1 - b + e + k))), {k, c, ∞}] Brutally specializing a=b=d=1, and changing s(k) = k*(k+e-1)^2 r(k)/(k+e) gives s[k]=k*(k+e-1), satisfying the recurrence s[k] == -((k^2 (-1 + e + k)^2)/(-2 k^2 - e (1 + 2 k) + s[1 + k])) , which is also obviously satisfied by ContinuedFractionK[-k^2 (-1 + e + k)^2, -2 k^2 - e (1 + 2 k), {k, c, ∞}]= (c (-1 + c + e) (PolyGamma[0, 1 + c] - PolyGamma[0, c + e]))/ (PolyGamma[0, c] - PolyGamma[0, -1 + c + e]) The general solution to the recurrence is s[k] -> 2 - e - 4 k + 2 e k + 2 k^2 - ((-1 + k) (-2 + e + k) (-1 + e + C[1] (HarmonicNumber[-2 + k] + PolyGamma[0, e] - PolyGamma[0, -2 + e + k])))/(-1 + e + EulerGamma C[1] + C[1] (PolyGamma[0, e] + PolyGamma[0, k] - PolyGamma[0, -1 + e + k]))}} which requires C[1]->0 for k*(k+e-1) and C[1] -> (1 - e)/(EulerGamma + PolyGamma[0, e]) for the correct value of the CF. Such an exotic C[1] makes it unclear how to use the original 3F2 to evaluate the original CF. ? --rwg

1 0

Re: [math-fun] {4, infinity} tiling of H^2 and a generalization of the mediant
by Henry Baker 05 Jul '12

05 Jul '12

This sounds extremely interesting, but I'm not familiar enough with the concepts; do you have an actual pictorial diagram? At 12:34 PM 7/4/2012, Mike Stay wrote: >In the Poincare half-plane model of hyperbolic 2-space, if we draw the >{3, infinity} regular tiling of the hyperbolic plane and put the three >points of one triangle at 0, 1, and infinity, then the rest of the >points land on Farey fractions. Since the sides are semicircles, each >triangle has one high side and two low sides. By placing a vertical >line at x, we can read off the continued fraction for x by looking at >which of the two low sides of each hyperbolic triangle it passes >through---that is, a sequence like LRRRLRRLLL becomes [0,1,3,1,2,3]. > >What points do we get with the {4, infinity} tiling? For every two >points, we'll get two new ones, a "mediant pair". In general, the >{n+2, infinity} tiling will have a notion of mediant that gives an >n-tuple of points. > >What's the corresponding notion of continued fraction? >-- >Mike Stay - metaweta(a)gmail.com >http://www.cs.auckland.ac.nz/~mike >http://reperiendi.wordpress.com

3 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

[math-fun] continuum version of vector problem
by Warren Smith 04 Jul '12

04 Jul '12

Hmm, ok, seems I did not make as craftmanlike a problem as I thought, sorry. DISCRETE VERSION: (2k)^n vectors, each n entries from +-{1,2,3,...,k}. Child replaces subset of vector entries by integers of same sign (or 0) and smaller absolute value. To prove: modified vectors still must have a nonempty subset which sums to 0-vector. SOLUTION: similar to the Alon Amit proof (which had been only for the case k=1). CONTINUUM VERSION: Real n dimensional vectors, each entry from real interval [-1,1]. I guess we had better exclude 0 though, otherwise the answer "use the 0-vector, which is immune to modification" kinds of screws things up. Child replaces subset of vector entries by reals of same sign (or 0) and smaller absolute value. To prove or disprove: modified vectors still must have a nonempty subset which sums to 0-vector. (NON)SOLUTION: Well... I should give you more time before reveal. But I believe I have a solution in which "sum" means what sum normally means, for any subset of cardinality which is either finite or countably infinite. I suspect one can also use same proof idea to work for where "sum" means "Lebesque integration" provided the child's mapping function obeys some kind of Lebesque-measurability postulates, but I'd need to bone up on that stuff. If the child's map function obeys other more restrictive postulates, then some other interesting stuff happens... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] continuum version of vector puzzle
by Warren Smith 03 Jul '12

03 Jul '12

Now consider the set of all vectors in n dimensions, each of whose entries lies in the real closed interval [-1,+1]. This is a solid hypercube. An evil child maliciously replaces some subset of the vector entries by reals of smaller absolute value. Prove or disprove that, no matter what the child does, some nonempty subset of the vectors still will exist that sums to the all-zero vector. (I think I have the answer with a proof, albeit my proof is still a bit sketchy... the definition of "add" can be a bit worrysome when the summands may form some weird, potentially nonmeasureable, set, so your solution will have more juice the more it understands about that.) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 3

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] Higgs boson
by Bill Gosper 02 Jul '12

02 Jul '12

Charge conjugation now requires CERN to find the Antichrist particle.

2 1

[math-fun] Permutations & Finite Groups in Lisp
by Robert Smith 02 Jul '12

02 Jul '12

Hey all: I just wanted to say that I've implemented code for manipulating permutations in Lisp in a library called CL-PERMUTATION. The more interesting thing perhaps is additional code for manipulating permutation groups. For example, you can generate random group elements, compute strong generators, test membership, calculate order, etc. It's not as complete or efficient as GAP, but it's in Lisp. Who doesn't want that? :) I want to try to integrate it with Maxima, but I don't know how to really do that at the moment. You can download the code and see the README which has examples here. https://bitbucket.org/tarballs_are_good/cl-permutation It includes for example a computation showing you can't flip a single edge on a Rubik's cube. Contributions are of course welcome. Cheers, Robert P.S., I'm also working on code (no where near complete) for manipulating real algebraic numbers. That might be more interesting for you folks whenever it gets done.

2 1

[math-fun] Permutations & Finite Groups in Lisp
by Bill Gosper 02 Jul '12

02 Jul '12

Back in the good old days of data execution, on the PDP6|10 (an intentionally Lisp-friendly architecture), I represented permutations as vectors of indexed PUSH instructions. Multiplied two n-vectors in n instructions. --rwg Quad> Hey all: I just wanted to say that I've implemented code for manipulating permutations in Lisp in a library called CL-PERMUTATION. The more interesting thing perhaps is additional code for manipulating permutation groups. For example, you can generate random group elements, compute strong generators, test membership, calculate order, etc. It's not as complete or efficient as GAP, but it's in Lisp. Who doesn't want that? :) I want to try to integrate it with Maxima, but I don't know how to really do that at the moment. You can download the code and see the README which has examples here. https://bitbucket.org/tarballs_are_good/cl-permutation It includes for example a computation showing you can't flip a single edge on a Rubik's cube. Contributions are of course welcome. Cheers, Robert P.S., I'm also working on code (no where near complete) for manipulating real algebraic numbers. That might be more interesting for you folks whenever it gets done.

1 0

[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