November 2011 - mathfun@mailman.xmission.com

[math-fun] Request for example elementary non-constructive proofs with "witnesses"
by Marc LeBrun 04 Dec '11

04 Dec '11

Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!

8 12

[math-fun] Convolution and continued fractions
by Bill Gosper 30 Nov '11

30 Nov '11

Mike Stay> It seems reasonable to think of continued fractions as generating a series of natural numbers. What's the convolution product on the series? Most generating functions are, well, functions. Is there a standard way of turning a continued fraction into a function? (Flajolet appears to have done a bunch of combinatorics work with continued fractions, but it's a little too dense for me to understand.) Rogers and Ramanujan showed how to q-deform continued fractions, replacing the 1/x step with q^n/x. From looking at continued fraction formulas for e and pi, however, it seems like for certain purposes we'd want linear or quadratic growth of the numerator instead of exponential. For the first case, an h-deformation that replaces the numerators with 1+nh instead of q^n seems promising. Has anyone seen work on that? -- Mike Stay - metaweta(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=metaweta%40gmail.com>http://www.cs.auckland.ac.nz/~mikehttp://reperiendi.wordpress.com This may not be quite what you're after, but a year or so back I posted valuations of some CFs with polynomial numerators and denominators as quotients of hypergeometric series. These were more "interesting" than the usual results where you build the CF from dividing out the middle term of a three term recurrence for the hypergeometric. Instead, my method was to write ODEs for the generating functions of the numerators and denominators of the convergents, solve them, and take limits. This promised to be quite tedious, except that it was possible to take "unconscionable shortcuts" (I think I called them). I think I can dig up some results, if you want. --rwg There was also a minor wrinkle on the Rogers-Ramanujan CF.

2 1

[math-fun] Convolution and continued fractions
by Mike Stay 30 Nov '11

30 Nov '11

It seems reasonable to think of continued fractions as generating a series of natural numbers. What's the convolution product on the series? Most generating functions are, well, functions. Is there a standard way of turning a continued fraction into a function? (Flajolet appears to have done a bunch of combinatorics work with continued fractions, but it's a little too dense for me to understand.) Rogers and Ramanujan showed how to q-deform continued fractions, replacing the 1/x step with q^n/x. From looking at continued fraction formulas for e and pi, however, it seems like for certain purposes we'd want linear or quadratic growth of the numerator instead of exponential. For the first case, an h-deformation that replaces the numerators with 1+nh instead of q^n seems promising. Has anyone seen work on that? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

1 0

Re: [math-fun] Puzzle from Emissary about number shrinkage via digit summation
by N. J. A. Sloane 30 Nov '11

30 Nov '11

For base 2, see A201219. Neil

1 0

[math-fun] 2nd kind Jacobi Amplitude?
by Bill Gosper 30 Nov '11

30 Nov '11

Am inverts F, the first kind elliptic integral. What inverts E, the second kind? Does it have any nice properties, like an ODE? --rwg

1 1

[math-fun] Puzzle from Emissary about number shrinkage via digit summation
by Warren Smith 30 Nov '11

30 Nov '11

actually a more careful look at my nonrigorous argument last post suggests that in radix R, the number of steps needed is only O(logR).

2 2

[math-fun] Puzzle from Emissary about number shrinkage via digit summation
by Warren Smith 30 Nov '11

30 Nov '11

>For every positive integer n, write it in binary, and allow the following possible set of transformations: You can insert "+" signs at arbitrary points within the binary expansion, and interpret that as a sum of binary numbers. For example 110101_2 --> 11_2+01_2+01_2 = 3 + 1 + 1 = 5 = 101_2. Show that there is an absolute constant C such that for any positive integer n there is a sequence of at most C such transformations that results in 1. Note: The minimal value of C is a real shocker This made me wonder about the obvious generalization to other bases, where now we ask for a sequence of such transformation that results in a single digit base b number. Victor Miller --Infuriating! OK, I will employ general radix R. Work backwards from the single-digit end-number. Let K denote a constant (which may change with different uses). In K backsteps we can reach any "sparse" number, meaning one with at most a constant number of nonzero digits. On the other hand (this time thinking forward) in 1 step where all the summands are either 1 or 2 or 3 digits long, we can reach (starting from a D-digit number) more than 1.6^D different numbers, each upperbounded by D*(D^3-1)<D^4. Well, obviously, for large D, that means most of the "different" numbers actually are the same, just got in different ways. There is vast overcoverage. Now if the original number was "random" then we can argue that with probability-->1 that EVERY number between about D*(R-1) and D^4 (or some not-too-shrunk subinterval of this to play it safe) is thus-reachable in 1 step. There are plenty of sparse numbers in that interval with only, say, 2, nonzero digits. They must be reachable in 1 step. We conclude that THEOREM: almost every number can reach a single-digit number in at most a constant number of steps (this works in any radix R>1, the constant is at most iteratedlogarithmic in R). "Almost every" means the fraction approaches 1. This however does not answer the puzzle because of the "almost". But I think one ought to be able to prove the approach to 1 is extremely fast asymptotically, prob=1-delta where delta=exponential(-D) small. Now if you believe that after a random step of our type, a nonrandom number gets randomized, then the probability we keep missing out on the gold (i.e. on the sparse numbers) for K consecutive steps no matter what steps we take ought to be exponential(-K*Dfinal) small, which for K of order R outweighs the factor R^Dfinal from counting Dfinal-digit numbers in radix R. Then there can be at most a finite number of exceptions because the probability that an exception exists shrinks small enough fast enough that the total number of exceptions ought to be finite. Unfortunately this paragraph seems likely to be unrigorizable. (The others look rigorizable.) Hence CONJECTURE: every number can reach a single-digit number in at most O(R) steps where this works in any radix R>1. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] A puzzle from Emissary
by Michael Reid 30 Nov '11

30 Nov '11

Thank you for the enjoyable puzzle. For now I will hold off on posting my solution unless there is some interest in seeing it. I do not know about higher bases, but it seems reasonable to believe that there is a bound -- depending upon the radix, but not on the initial number -- for the number of steps needed. My solution for the base 2 case does not seem to adapt easily, if it all, to other bases. > In the lastest issue of Emissary (the newsletter from MSRI) there's the > following challenging puzzle: > > For every positive integer n, write it in binary, and allow the following > possible set of transformations: > > You can insert "+" signs at arbitrary points within the binary expansion, > and interpret that as a sum of binary numbers. For example > > 110101_2 --> 11_2+01_2+01_2 = 3 + 1 + 1 = 5 = 101_2. > > Show that there is an absolute constant C such that for any positive > integer n there is a sequence of at most C such transformations that > results in 1. > > Note: The minimal value of C is a real shocker > > This made me wonder about the obvious generalization to other bases, where > now we ask for a sequence of such transformation that results in a single > digit base b number. > > Victor >

2 1

Re: [math-fun] http://en.wikipedia.org/wiki/Golden_ratio
by Bill Gosper 29 Nov '11

29 Nov '11

Many thanks for that background. Well, I don't need a tug-of-war with some crank, especially when there is so much to be done for the Dragon Curve page. Hey, to go along with ChebyshevU[n, I/2]/I^n == Fibonacci[n + 1] I just rediscovered Hypergeometric2F1[1/2 - n/2, 1 - n/2, 3/2, 5]*n/2^(n - 1) == Fibonacci[n] which terminates after n/2 terms. No sqrts. --rwg (Here's the zippy golden ratio without the +1/2: Sum[(((50250675141714*n + 100501350283429/2)* Binomial[2*n, n])/((n + 1)*62113250390420^n)), {n, 0, Infinity}]/31056625195210 Now we need a theological argument that this is the One True Series.) --------------------- That infinite series was added in January 2010 by an anonymous user from IP address 69.133.204.190, who rather tenaciously added it three times, I think. One of them (http://en.wikipedia.org/w/index.php?title=Golden_ratio&diff=prev&oldid=3355…) included a citation, to Brian Roselle, https://sites.google.com/site/goldenmeanseries/ a somewhat self-important-seeming diatribe claiming that "While investigating the Golden Mean, no equivalent infinite series was found that explicitely defined" it. I won't speculate on what Brian Roselle's IP address might or might not be. It's Wikipedia -- go ahead and improve the article, that's what it's all about... --Michael Kleber

2 1

Re: [math-fun] A problem about approximation
by Warren Smith 29 Nov '11

29 Nov '11

>I'd suggest targeting abs(x-.5), or max(x,.5). Then you could go after piecewise linear, which would solve your puzzle. OTOH, if you can't do abs or max, you've got a negative answer. --The ASU approximation puzzle has been solved (by me) I think... the proof still could use a little fleshing out, but I think it is valid and it also is interesting... you can read it in section 8 of this pre-paper http://dl.dropbox.com/u/3507527/SpeechProc.html which also explains where this puzzle came from and what it is useful for (ASU stands for Aho Steiglitz Ullman). >You don't mention the 'closed under composition' property. >Rich --good point, will do.

1 0